Version 1.1.0

1st November 2012

Recent Changes

Code Download

  • Integer

HSL_MC79 Sparse matrix: maximum matching and Dulmage-Mendelsohn decomposition

Given the sparsity pattern of a rectangular sparse matrix A = {aij}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 fine Dulmage-Mendelsohn decomposition are available.

A matching is a set of the rows β„› and columns π’ž, where each row in i β„› is paired with a unique j π’ž subject to aij0. The size of a matching is defined to be equal to the number of columns in π’ž. 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

PAQ = β„›1 β„›2 β„›3 π’ž1π’ž2π’ž3 A1A4A6 0 A2A5 0 0 A3 ,

where A1, formed by the rows in the set β„›1 and the columns in the set π’ž1, is an underdetermined matrix with m1 rows and n1 columns (m1 < n1 or m1 = n1 = 0); A2, formed by the rows in the set β„›2 and the columns in the set π’ž2, is a square, well-determined matrix with m2 rows; A3, formed by the rows in the set β„›3 and the columns in the set π’ž3, is an overdetermined matrix with m3 rows and n3 columns (m3 > n3 or m3 = n3 = 0). In particular, let the set of rows β„› and the set of columns π’ž form a maximum matching of A. The sets β„›1 and β„›2 are subsets of β„›, and β„›3 β„› has n3 entries. The sets π’ž2 and π’ž3 are subsets of π’ž, and π’ž1 π’ž has m1 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 A1 and A3 are block diagonal and each diagonal block is irreducible, and A2 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.