HSL_MC79: Sparse matrix: maximum matching and Dulmage-Mendelsohn decomposition

Given the sparsity pattern of a rectangular sparse matrix \(A = \{ a_{ij} \}_{m\times n},\) HSL_MC79 has entries to compute a maximum matching, and a row permutation \(P\) and column permutation \(Q\) such that \(PAQ\) is of block triangular form: a coarse Dulmage-Mendelsohn decomposition and a fine Dulmage-Mendelsohn decomposition are available.

A matching is a set of the rows \(\mathcal{R}\) and columns \(\mathcal{C},\) where each row in \(i\in\mathcal{R}\) is paired with a unique \(j\in\mathcal{C}\) subject to \(a_{ij}\neq 0.\) The size of a matching is defined to be equal to the number of columns in \({\mathcal{C}}.\) A maximum matching of \(A\) is a matching of \(A\) that has size greater than or equal to any other matching of \(A.\) The size of the maximum matching is equal to the structural rank of the matrix.

The Dulmage-Mendelsohn decomposition consists of a row permutation \(P\) and a column permutation \(Q\) such that \[\begin{aligned} P A Q = \begin{array}{r} \\ \begin{array}{r} \mathcal{R}_{1} \\ \mathcal{R}_2 \\ \mathcal{R}_3 \end{array} \end{array} \begin{array}{c} \left. \begin{array}{rrr} \mathcal{C}_{1} & \mathcal{C}_2 & \mathcal{C}_3 \end{array}\right. \\ \left[ \begin{array}{ccc} A_{1} & A_{4} & A_{6} \\ 0 & A_{2} & A_{5} \\ 0 & 0 & A_{3} \end{array} \right]\end{array},\end{aligned}\] where \(A_1,\) formed by the rows in the set \(\mathcal{R}_1\) and the columns in the set \(\mathcal{C}_1,\) is an underdetermined matrix with \(m_1\) rows and \(n_1\) columns (\(m_1 < n_1\) or \(m_1=n_1=0\)); \(A_2,\) formed by the rows in the set \(\mathcal{R}_2\) and the columns in the set \(\mathcal{C}_2,\) is a square, well-determined matrix with \(m_2\) rows; \(A_3,\) formed by the rows in the set \(\mathcal{R}_3\) and the columns in the set \(\mathcal{C}_3,\) is an overdetermined matrix with \(m_3\) rows and \(n_3\) columns (\(m_3 > n_3\) or \(m_3=n_3=0\)). In particular, let the set of rows \(\mathcal{R}\) and the set of columns \(\mathcal{C}\) form a maximum matching of \(A.\) The sets \(\mathcal{R}_1\) and \(\mathcal{R}_2\) are subsets of \(\mathcal{R},\) and \(\mathcal{R}_3\cap\mathcal{R}\) has \(n_3\) entries. The sets \(\mathcal{C}_2\) and \(\mathcal{C}_3\) are subsets of \(\mathcal{C},\) and \(\mathcal{C}_1\cap\mathcal{C}\) has \(m_1\) entries.

The coarse Dulmage-Mendelsohn decomposition orders the unmatched columns as the first columns in \(PAQ\) and orders the unmatched rows as the last rows in \(PAQ.\) The output from the coarse Dulmage-Mendelsohn decomposition can be used to find a node separator from an edge separator of a graph.

The fine Dulmage-Mendelsohn decomposition computes a row permutation \(P\) and a column permutation \(Q\) such that \(A_1\) and \(A_3\) are block diagonal and each diagonal block is irreducible, and \(A_2\) is block upper triangular with strongly connected (square) diagonal blocks. If \(A\) is reducible and nonsingular, the fine Dulmage-Mendelsohn decomposition of a matrix \(A\) can be used to solve the linear systems \(Ax=b\) with block back-substitution.