# dmperm

Dulmage-Mendelsohn decomposition

## Syntax

```p = dmperm(A) [p,q,r,s,cc,rr] = dmperm(A) ```

## Description

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

## Tips

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

## References

 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.