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