逆带宽减少的稀疏矩阵：更快或更慢

Question

我有一个大小为 1393 x 1393 的邻接矩阵，它看起来像：

我正在根据这个矩阵做空间建模，后面会涉及到密集的矩阵求逆。听说对于这样的稀疏矩阵，我们可以将行和列重新排序以达到最小带宽，这将大大减少矩阵求逆所需的时间。我找到的算法叫做 Gibbs-Poole-Stockmeyer，我找到了一个 FORTRAN implementation

我是 R 用户，目前正致力于在 R 中调用这个旧的 FORTRAN 代码，但没有成功（仍在尝试）。所以我的问题是：

当使用R/Rcpparmadillo时，如果减少带宽，稀疏矩阵的矩阵求逆会更容易吗？我是否需要任何明确的命令来告诉 R 如何求逆矩阵或者它只是自然发生的。
谁能帮我在 R 中使用 FORTRAN 代码？我仍在尝试并将错误上传到我这边。

谢谢！

编辑：我找到了另一种算法：Cuthill–McKee 算法，目的相同。这个问题属于图论领域。在 R 包的帮助下：RBGL，我设法通过重命名图中的顶点来重新排序原始矩阵的行和列，并具有新结构：但是，当我测试矩阵求逆的计算时间时，没有区别：Bmat 是旧矩阵，而 new_B 是带宽减少的矩阵。

n = dim(Bmat)[1]
IrhoC = diag(n) - 0.1 * Bmat
IrhoC2 = diag(n) - 0.1 * new_B
library(microbenchmark)
microbenchmark(
  old = chol2inv(chol(IrhoC)),
  new = chol2inv(chol(IrhoC2)),
  solve_old = chol2inv(chol(IrhoC)),
  solve_new = chol2inv(chol(IrhoC2)),
  times = 10
)
Unit: milliseconds
      expr      min       lq      mean   median       uq       max neval cld
       old 59.66203 65.81924 106.55729 82.68835 94.74017 346.38852    10   a
       new 68.26124 76.63195  82.13040 81.81659 87.03293  97.39588    10   a
 solve_old 65.39816 79.67434  82.78533 85.27720 89.92952  94.98980    10   a
 solve_new 60.42481 64.97768  77.97695 77.98818 87.53069  99.21062    10   a

原来那些矩阵求逆是没有时间差的。在这一点上，我不知道需要什么样的 commands/options 才能利用新的减少带宽矩阵。

Answer 1

希望这仍然有用。

您可能没有发现差异，因为调用的 Cholesky 方法是标准方法，即不是为稀疏（重新排序）矩阵设计的。我发现了一种似乎在 scikit.sparse 库 (Python) 中有效的方法。但是，您的问题与以下示例非常相似：Rue and Held,2005 , "Gaussian Markov Random Fields (GMRF) / Theory and applications"（第 2.5 节）。他们为 GMRFs 发布了一个名为：GMRFLib 的 R 包，希望它能满足您的需求。

逆带宽减少的稀疏矩阵：更快或更慢

Inverse a sparse matrix with reduced bandwidth: faster or not

r

sparse-matrix

matrix-inverse