Note: This page has been translated by MathWorks. Please click here

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

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

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

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

Was this topic helpful?