Main Content

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.