密集矩阵与稀疏矩阵代数的速度比较

Question

我将使用R语言处理一个非常稀疏的矩阵（7 e6 x 4.5 e3）。因此，我正在尝试了解如何高效地处理稀疏矩阵。我有两个相关的问题。

首先，我了解到Matrix包会自动链接到LAPACK和SuiteSparse编译的dll文件。（我在Windows上工作。）我认为相比使用LAPACK套件中的密集矩阵，使用SuiteSparse程序会缩短执行时间。但是下面的测试运行表明，稀疏矩阵版本的运行时间比密集版本慢得多。

> library(Matrix)
> sparse <- sparseMatrix(1:4, 1:4, x=rnorm(4))
> dense <- as.matrix(sparse)
> x <- 1:4
> system.time(for (i in 1:10000) sparse %*% x)
   user  system elapsed 
   0.23    0.00    0.23 
> system.time(for (i in 1:10000) dense %*% x)
   user  system elapsed 
      0       0       0 
> system.time(for (i in 1:1000) solve(sparse))
   user  system elapsed 
   3.94    0.00    3.94 
> system.time(for (i in 1:1000) solve(dense))
   user  system elapsed 
   0.05    0.00    0.05

a) 我理解正确，Matrix会自动连接上述两个已编译的库吗？如果不是，我应该如何链接这些DLL文件？ b) 一般而言，使用稀疏矩阵代数比使用密集矩阵代数慢吗？

其次：我已经安装了RcppEigen和RcppArmadillo软件包。我已经成功编译了一个带有RcppArmadillo的测试程序（使用Dirk Eddelbuettel和Conrad Sanderson的论文）。但是，我一直找不到类似于RcppEigen的介绍性文件，该文件可以为我提供一些模板代码，以便我开始使用。你们中是否有人能指向像Eddelbuettel和Sanderson论文那样的文档，以帮助我入门RcppEigen？

- Larry Hunsicker

---

您的第二个问题是一个关于离线资源的请求（虽然有人可能会在评论中回答，但技术上来说这不是 StackOverflow 的主题）。 - Ben Bolker

Answer 1

（这段内容略长无法作为评论。）我建议针对更大的矩阵进行分析；我可以想象，当矩阵比较小并且不是非常稀疏时（例如本例中25%的单元格为非零），稀疏算法处于劣势。在下面的示例中（1000x1000矩阵），稀疏解算器比密集解算器快26倍。您可能会发现Matrix例程已足够快，而不需要承担学习(Rcpp)Eigen/(Rcpp)Armadillo的额外认知负荷...

library(rbenchmark)
library(Matrix)
set.seed(101)
sparse <- sparseMatrix(1:1000,1:1000,x=rnorm(1000))
dense <- as.matrix(sparse)
benchmark(solve(sparse),solve(dense),replications=20,
          columns = c(
       "test", "replications", "elapsed", "relative", "user.self"))
##            test replications elapsed relative user.self
## 2  solve(dense)           20   6.932   26.868     6.692
## 1 solve(sparse)           20   0.258    1.000     0.256

- Ben Bolker

---

谢谢，Ben！你让我的生活变得更加轻松了。 - Larry Hunsicker