r - 是否有适当的 Cuthill Mckee 为 R 重新排序？

Question

我有一个具有以下稀疏结构的拉格朗日矩阵：

这是矩阵稀疏结构

我想使用 Cuthill Mckee 排序，但我真的不知道如何在 R 中使用它。我发现了 2 种可能的算法：

• https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/Ordering 但是这个要求的是图表而不是矩阵
• https://rdrr.io/bioc/netprioR/man/cuthill_mckee.html但 R 说它找不到它并在 R 中输入 ??cuthill_mckee 会给出一个空白页。

有人对此有经验吗？

标签： rsparse-matrixbandwidth

Answer 1

安装并加载 netprioR 包后，该功能应该可用。不过，它似乎没有导出，因此您必须将其称为netprioR:::cuthill_mckee(x).

从该包的源代码：

#' Cuthill McKee (CM) algorithm
#' 
#' Transform sparse matrix into a band matrix
#' 
#' @author Fabian Schmich
#' @import Matrix
#' @param x Input matrix
#' @return Band matrix
cuthill_mckee <- function(x) {
  degs <- data.frame(Idx=1:ncol(x), NonZero=apply(x, 1, function(x) length(which(x != 0))))
  R <- degs$Idx[which.min(degs$NonZero)]
  i <- 1
  for (i in 1:ncol(x)) {
    Ai <- setdiff(which(x[R[i],] != 0), R)
    if (length(Ai) > 0) {
      Ai <- Ai[order(degs$NonZero[Ai], decreasing = FALSE)]
      R <- append(R, Ai)
    } else {
      R <- append(R, degs$Idx[-R][which.min(degs$NonZero[-R])])
    }
    i <- i + 1
  }
  rR <- rev(R)
  return(x[rR, rR])
}