 ## Version 1.1.1

15th November 2022

# 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.