dmperm function

Dulmage-Mendelsohn Permutation / Decomposition

For any $n * m$ (typically) sparse matrix x

compute the Dulmage-Mendelsohn 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)

Arguments

• x: a typically sparse matrix; internally coerced to either "dgCMatrix" or "dtCMatrix".
• nAns: an integer specifying the length of the resulting list. Must be 2, 4, or 6.
• seed: an integer code in -1,0,1; determining the (initial) permutation; by default, seed = 0, no (or the identity) permutation; seed = -1 uses the reverse permutation k:1; for seed = 1, it is a random permutation (using R's RNG, seed, etc).

Details

See the book section by Tim Davis; page 122--127, in the References.

Returns

a named list with (by default) 6 components, - p: integer vector with the permutation p, of length nrow(x).

• q: integer vector with the permutation q, of length ncol(x).

• r: integer vector of length nb+1, where block k is rows r[k] to r[k+1]-1 in A[p,q].

• s: integer vector of length nb+1, where block k is cols s[k] to s[k+1]-1 in A[p,q].

• rr5: integer vector of length 5, defining the coarse row decomposition.

• cc5: integer vector of length 5, defining the coarse column decomposition.

References

Section 7.4 Dulmage-Mendelsohn decomposition, pp. 122 ff of

Timothy A. Davis (2006) Direct Methods for Sparse Linear Systems, SIAM Series Fundamentals of Algorithms .

Author(s)

Martin Maechler, with a lot of encouragement by Mauricio Vargas.

See Also

Schur, the class of permutation matrices; "pMatrix".

Examples

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)) # non-random 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))
})