Given the sparsity pattern of a rectangular sparse matrix $A={\left\{{a}_{ij}\right\}}_{m\Gamma \x97n},$ 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 ο¬ne Dulmage-Mendelsohn decomposition are available.

A matching is a set of the rows $\mathcal{\beta \x84\x9b}$ and columns $\mathcal{\pi \x9d\x92\x9e},$ where each row in $i\in \mathcal{\beta \x84\x9b}$ is paired with a unique $j\in \mathcal{\pi \x9d\x92\x9e}$ subject to ${a}_{ij}\ne 0.$ The size of a matching is deο¬ned to be equal to the number of columns in $\mathcal{\pi \x9d\x92\x9e}.$ 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{array}{rcll}PAQ=\begin{array}{c}\hfill \\ \hfill \begin{array}{c}\hfill {\mathcal{\beta \x84\x9b}}_{1}\\ \hfill {\mathcal{\beta \x84\x9b}}_{2}\\ \hfill {\mathcal{\beta \x84\x9b}}_{3}\end{array}\end{array}\begin{array}{c}\hfill \begin{array}{ccc}\hfill {\mathcal{\pi \x9d\x92\x9e}}_{1}& \hfill {\mathcal{\pi \x9d\x92\x9e}}_{2}& \hfill {\mathcal{\pi \x9d\x92\x9e}}_{3}\end{array}\hfill \\ \hfill \left[\begin{array}{ccc}\hfill {A}_{1}\hfill & \hfill {A}_{4}\hfill & \hfill {A}_{6}\hfill \\ \hfill 0\hfill & \hfill {A}_{2}\hfill & \hfill {A}_{5}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill {A}_{3}\hfill \end{array}\right]\hfill \end{array},& & & \text{}\end{array}$$where ${A}_{1},$ formed by the rows in the set ${\mathcal{\beta \x84\x9b}}_{1}$ and the columns in the set ${\mathcal{\pi \x9d\x92\x9e}}_{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{\beta \x84\x9b}}_{2}$ and the columns in the set ${\mathcal{\pi \x9d\x92\x9e}}_{2},$ is a square, well-determined matrix with ${m}_{2}$ rows; ${A}_{3},$ formed by the rows in the set ${\mathcal{\beta \x84\x9b}}_{3}$ and the columns in the set ${\mathcal{\pi \x9d\x92\x9e}}_{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{\beta \x84\x9b}$ and the set of columns $\mathcal{\pi \x9d\x92\x9e}$ form a maximum matching of $A.$ The sets ${\mathcal{\beta \x84\x9b}}_{1}$ and ${\mathcal{\beta \x84\x9b}}_{2}$ are subsets of $\mathcal{\beta \x84\x9b},$ and ${\mathcal{\beta \x84\x9b}}_{3}\cap \mathcal{\beta \x84\x9b}$ has ${n}_{3}$ entries. The sets ${\mathcal{\pi \x9d\x92\x9e}}_{2}$ and ${\mathcal{\pi \x9d\x92\x9e}}_{3}$ are subsets of $\mathcal{\pi \x9d\x92\x9e},$ and ${\mathcal{\pi \x9d\x92\x9e}}_{1}\cap \mathcal{\pi \x9d\x92\x9e}$ has ${m}_{1}$ entries.

The coarse Dulmage-Mendelsohn decomposition orders the unmatched columns as the ο¬rst 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 ο¬nd a node separator from an edge separator of a graph.

The ο¬ne 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 ο¬ne Dulmage-Mendelsohn decomposition of a matrix $A$ can be used to solve the linear systems $Ax=b$ with block back-substitution.