dmperm {Matrix}  R Documentation 
For any n \times m
(typically) sparse matrix x
compute the DulmageMendelsohn row and columns permutations which at
first splits the n
rows and m
columns into coarse partitions
each; and then a finer one, reordering rows and columns such that the
permutated matrix is “as upper triangular” as possible.
dmperm(x, nAns = 6L, seed = 0L)
x 
a typically sparse matrix; internally coerced to either

nAns 
an integer specifying the 
seed 
an integer code in 1,0,1; determining the (initial)
permutation; by default, 
See the book section by Tim Davis; page 122–127, in the References.
a named list
with (by default) 6 components,
p 
integer vector with the permutation 
q 
integer vector with the permutation 
r 
integer vector of length 
s 
integer vector of length 
rr5 
integer vector of length 5, defining the coarse row decomposition. 
cc5 
integer vector of length 5, defining the coarse column decomposition. 
Martin Maechler, with a lot of “encouragement” by Mauricio Vargas.
Section 7.4 DulmageMendelsohn decomposition, pp. 122 ff of
Timothy A. Davis (2006)
Direct Methods for Sparse Linear Systems, SIAM Series
“Fundamentals of Algorithms”.
Schur
, the class of permutation matrices; "pMatrix"
.
set.seed(17)
(S9 < rsparsematrix(9, 9, nnz = 10, symmetric=TRUE)) # dsCMatrix
str( dm9 < dmperm(S9) )
(S9p < with(dm9, S9[p, q]))
## looks good, but *not* quite upper triangular; these, too:
str( dm9.0 < dmperm(S9, seed=1)) # nonrandom too.
str( dm9_1 < dmperm(S9, seed= 1)) # a random one
## The last two permutations differ, but have the same effect!
(S9p0 < with(dm9.0, S9[p, q])) # .. hmm ..
stopifnot(all.equal(S9p0, S9p))# same as as default, but different from the random one
set.seed(11)
(M < triu(rsparsematrix(9,11, 1/4)))
dM < dmperm(M); with(dM, M[p, q])
(Mp < M[sample.int(nrow(M)), sample.int(ncol(M))])
dMp < dmperm(Mp); with(dMp, Mp[p, q])
set.seed(7)
(n7 < rsparsematrix(5, 12, nnz = 10, rand.x = NULL))
str( dm.7 < dmperm(n7) )
stopifnot(exprs = {
lengths(dm.7[1:2]) == dim(n7)
identical(dm.7, dmperm(as(n7, "dMatrix")))
identical(dm.7[1:4], dmperm(n7, nAns=4))
identical(dm.7[1:2], dmperm(n7, nAns=2))
})