Optimal weighted matchings for rank-deficient sparse matrices

ePubs

The open archive for STFC research publications

Persistent URL	http://purl.org/net/epubs/work/63153
Record Status	Checked
Record Id	63153
Title	Optimal weighted matchings for rank-deficient sparse matrices
Contributors	JD Hogg (STFC Rutherford Appleton Lab.), JA Scott (STFC Rutherford Appleton Lab.)
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
Keywords
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