Version 1.1.1
15th November 2022 User documentation
 Recent Changes

Code Download
 Integer
HSL_MC79: Sparse matrix: maximum matching and DulmageMendelsohn 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 DulmageMendelsohn decomposition and a fine DulmageMendelsohn 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 DulmageMendelsohn 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, welldetermined 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 DulmageMendelsohn 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 DulmageMendelsohn decomposition can be used to find a node separator from an edge separator of a graph.
The fine DulmageMendelsohn 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 DulmageMendelsohn decomposition of a matrix \(A\) can be used to solve the linear systems \(Ax=b\) with block backsubstitution.