## Version 1.1.0

1st November 2012

Recent Changes

• Integer

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

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

A matching is a set of the rows $\mathsc{ℛ}$ and columns $\mathsc{𝒞},$ where each row in $i\in \mathsc{ℛ}$ is paired with a unique $j\in \mathsc{𝒞}$ subject to ${a}_{ij}\ne 0.$ The size of a matching is deﬁned to be equal to the number of columns in $\mathsc{𝒞}.$ 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 {\mathsc{ℛ}}_{1}\\ \hfill {\mathsc{ℛ}}_{2}\\ \hfill {\mathsc{ℛ}}_{3}\end{array}\end{array}\begin{array}{c}\hfill \begin{array}{ccc}\hfill {\mathsc{𝒞}}_{1}& \hfill {\mathsc{𝒞}}_{2}& \hfill {\mathsc{𝒞}}_{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 ${\mathsc{ℛ}}_{1}$ and the columns in the set ${\mathsc{𝒞}}_{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 ${\mathsc{ℛ}}_{2}$ and the columns in the set ${\mathsc{𝒞}}_{2},$ is a square, well-determined matrix with ${m}_{2}$ rows; ${A}_{3},$ formed by the rows in the set ${\mathsc{ℛ}}_{3}$ and the columns in the set ${\mathsc{𝒞}}_{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 $\mathsc{ℛ}$ and the set of columns $\mathsc{𝒞}$ form a maximum matching of $A.$ The sets ${\mathsc{ℛ}}_{1}$ and ${\mathsc{ℛ}}_{2}$ are subsets of $\mathsc{ℛ},$ and ${\mathsc{ℛ}}_{3}\cap \mathsc{ℛ}$ has ${n}_{3}$ entries. The sets ${\mathsc{𝒞}}_{2}$ and ${\mathsc{𝒞}}_{3}$ are subsets of $\mathsc{𝒞},$ and ${\mathsc{𝒞}}_{1}\cap \mathsc{𝒞}$ 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.