Dulmage-Mendelsohn decomposition
p = dmperm(A)
[p,q,r,s,cc,rr] = dmperm(A)
p = dmperm(A) finds a vector p such
that p(j) = i if column j is
matched to row i, or zero if column j is
unmatched. If A is a square matrix with full structural
rank, p is a maximum matching row permutation and A(p,:) has
a zero-free diagonal. The structural rank of A is sprank(A)
= sum(p>0).
[p,q,r,s,cc,rr] = dmperm(A) where A need
not be square or full structural rank, finds the Dulmage-Mendelsohn
decomposition of A. p and q are
row and column permutation vectors, respectively, such that A(p,q) has
a block upper triangular form. r and s are
index vectors indicating the block boundaries for the fine decomposition.
cc and rr are vectors of length
five indicating the block boundaries of the coarse decomposition.
C = A(p,q) is split into a 4-by-4 set
of coarse blocks:
A11 A12 A13 A14 0 0 A23 A24 0 0 0 A34 0 0 0 A44
A12, A23, and A34 are square with
zero-free diagonals. The columns of A11 are the unmatched columns, and the
rows of A44 are the unmatched rows. Any of these blocks can be empty. In the
coarse decomposition, the (i,j)th block is
C(rr(i):rr(i+1)-1,cc(j):cc(j+1)-1). If A is square and
structurally nonsingular, then A23 = C. That is, all of the other coarse
blocks are 0-by-0.For a linear system:
[A11 A12] is the underdetermined part of the system—it is
always rectangular and with more columns than rows, or is
0-by-0.
A23 is the well-determined part of the system—it is always
square. The A23 submatrix is further subdivided into block upper triangular
form via the fine decomposition (the strongly connected components of
A23).
[A34; A44] is the overdetermined part of the system—it is
always rectangular with more rows than columns, or is
0-by-0.
The structural rank of A is sprank(A) =
rr(4)-1, which is an upper bound on the numerical rank of A.
sprank(A) = rank(full(sprand(A))) with probability 1 in exact
arithmetic.
C(r(i):r(i+1)-1,s(j):s(j+1)-1) is the (i,j)th
block of the fine decomposition. The (1,1) block
is the rectangular block [A11 A12], unless this
block is 0-by-0. The (b,b) block
is the rectangular block [A34 ; A44], unless this
block is 0-by-0, where b
= length(r)-1. All other blocks of the form C(r(i):r(i+1)-1,s(i):s(i+1)-1) are
diagonal blocks of A23, and are square with a zero-free
diagonal.
If A is a reducible matrix, the linear system Ax =
b can be solved by permuting A to a block upper
triangular form, with irreducible diagonal blocks, and then performing block back-substitution.
Only the diagonal blocks of the permuted matrix need to be factored, saving fill and arithmetic
in the blocks above the diagonal.
In graph theoretic terms, dmperm finds a maximum-size matching in the
bipartite graph of A, and the diagonal blocks of A(p,q)
correspond to the strong Hall components of that graph. The output of dmperm
can also be used to find the connected or strongly connected components of an undirected or
directed graph. For more information see Pothen and Fan [1].
[1] Pothen, Alex and Chin-Ju Fan “Computing the Block Triangular Form of a Sparse Matrix” ACM Transactions on Mathematical Software Vol 16, No. 4 Dec. 1990, pp. 303-324.