Optimal Weighted Matchings for Rank-Deficient Sparse Matrices
Jonathan D. Hogg, J. A. Scott · SIAM Journal on Matrix Analysis and Applications · 2013
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 $\mathcal{I}\times\mathcal{J}$ of rows and columns such that the restriction of $A$ to $\mathcal{I}\times\mathcal{I}$ is nonsingular but, in general, the chosen $\mathcal{I}$ is suboptimal. In this paper, we propose modifying the approach to obtain an optimal $\mathcal{I}$. We focus on the symmetric case and present results for rank-deficient sparse symmetric matrices arising from practical applications.