Given the sparsity pattern of a rectangular sparse matrix HSL_MC79 has entries to compute a maximum matching, and a row permutation and column permutation such that 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 and columns where each row in is paired with a unique subject to The size of a matching is deﬁned to be equal to the number of columns in A maximum matching of is a matching of that has size greater than or equal to any other matching of The size of the maximum matching is equal to the structural rank of the matrix.
The Dulmage-Mendelsohn decomposition consists of a row permutation and a column permutation such that
where formed by the rows in the set and the columns in the set is an underdetermined matrix with rows and columns ( or ); formed by the rows in the set and the columns in the set is a square, well-determined matrix with rows; formed by the rows in the set and the columns in the set is an overdetermined matrix with rows and columns ( or ). In particular, let the set of rows and the set of columns form a maximum matching of The sets and are subsets of and has entries. The sets and are subsets of and has entries.
The coarse Dulmage-Mendelsohn decomposition orders the unmatched columns as the ﬁrst columns in and orders the unmatched rows as the last rows in 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 and a column permutation such that and are block diagonal and each diagonal block is irreducible, and is block upper triangular with strongly connected (square) diagonal blocks. If is reducible and nonsingular, the ﬁne Dulmage-Mendelsohn decomposition of a matrix can be used to solve the linear systems with block back-substitution.