The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/63153
Record Status Checked
Record Id 63153
Title Optimal weighted matchings for rank-deficient sparse matrices
Abstract The maximum matching of a sparse matrix A that maximizes the product of the matched entries can be used to increase the speed and reliability of sparse linear algebra operations. One popular method of solution is to transform to an assignment problem and to use a sparse variant of the Hungarian algorithm. If A is structurally rank deficient this approach chooses a set I x J of rows and columns such that the restriction of A to I x I is non-singular but, in general, the chosen I is sub-optimal. In this paper, we propose modifying the approach to obtain an optimal I. We focus on the symmetric case and present results for rank-deficient sparse symmetric matrices arising from practical applications.
Organisation STFC , SCI-COMP
Funding Information
Related Research Object(s): 11445454
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Preprints RAL-P-2012-003. 2012. RAL-P-2012-003.pdf 2012
Journal Article SIAM J Matrix Anal A 34, no. 4 (2013): 1431-1447. http://dx.doi.org/10.1137/120884262 2013