## Documentation Center |

Dulmage-Mendelsohn decomposition

`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

where `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)`. For a linear
system,

`[A11 A12]`is the underdetermined part of the system—it is always rectangular and with more columns and rows, or`0`-by-`0`,`A23`is the well-determined part of the system—it is always square, and`[A34 ; A44]`is the overdetermined part of the system—it is always rectangular with more rows than columns, or`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.

The `A23` submatrix is further subdivided into
block upper triangular form via the fine decomposition (the strongly
connected components of `A23`). If `A` is
square and structurally nonsingular, `A23` is the
entire matrix.

`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.

[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.

Was this topic helpful?