p = dmperm(A)
[p,q,r,s,cc,rr] = dmperm(A)
p = dmperm(A) finds a vector
p(j) = i if column
matched to row
i, or zero if column
A is a square matrix with full structural
p is a maximum matching row permutation and
a zero-free diagonal. The structural rank of
[p,q,r,s,cc,rr] = dmperm(A) where
not be square or full structural rank, finds the Dulmage-Mendelsohn
row and column permutation vectors, respectively, such that
a block upper triangular form.
index vectors indicating the block boundaries for the fine decomposition.
rr are vectors of length
five indicating the block boundaries of the coarse decomposition.
C = A(p,q) is split into a
of coarse blocks:
A11 A12 A13 A14 0 0 A23 A24 0 0 0 A34 0 0 0 A44
A34are square with zero-free diagonals. The columns of
A11are the unmatched columns, and the rows of
A44are the unmatched rows. Any of these blocks can be empty. In the coarse decomposition, the
Ais square and structurally nonsingular, then
A23 = C. That is, all of the other coarse blocks are
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
A23is the well-determined part of the system—it is always square. The
A23submatrix is further subdivided into block upper triangular form via the fine decomposition (the strongly connected components of
[A34; A44]is the overdetermined part of the system—it is always rectangular with more rows than columns, or is
The structural rank of
rr(4)-1, which is an upper bound on the numerical rank of
sprank(A) = rank(full(sprand(A))) with probability 1 in exact
C(r(i):r(i+1)-1,s(j):s(j+1)-1) is the
block of the fine decomposition. The
is the rectangular block
[A11 A12], unless this
is the rectangular block
[A34 ; A44], unless this
= length(r)-1. All other blocks of the form
diagonal blocks of
A23, and are square with a zero-free
Ais a reducible matrix, the linear system Ax = b can be solved by permuting
Ato 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,
dmpermfinds 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
dmpermcan also be used to find the connected or strongly connected components of an undirected or directed graph. For more information see Pothen and Fan .
 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.
 Davis, Timothy A. Direct Methods for Sparse Linear Systems. SIAM Series on the Fundamentals of Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2006.
Run code in the background using MATLAB®
backgroundPool or accelerate code with Parallel Computing Toolbox™
This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.
Introduced before R2006a