C++如何解决非常大的稀疏线性系统

Question

我正在尝试用 C++ 求解一个非常大且稀疏的线性方程组。目前，我正在使用 eigen 的 BiCGSTAB。它适用于小矩阵，但对于我需要的大小的矩阵，它花费了太多时间，即 40804x40804(将来可能更大)。

我有一个很长的脚本，但我只是使用了以下格式:

SparseMatrix<double> sj(40804,40804);
VectorXd c_(40804), sf(40804);
sj.reserve(VectorXi::Constant(40804,36)); //This is a very good estimate of how many non zeros in each column
//...Fill in actual number in sj
sj.makeCompressed();
BiCGSTAB<SparseMatrix<double> > handler;
//...Fill in sj, only in the entries that have been initialized previously
handler.analyzePattern(sj)
handler.factorize(sj);
c_.setZero();
c_=handler.solve(sf);

这花费的时间太长了!是的，解决方案确实存在。 matlab 中的稀疏函数似乎可以很好地处理这个问题，但我在 C++ 中需要它才能连接到服务器。

如果你能帮助我，我将不胜感激!

Answer 1

您应该考虑使用一种高级稀疏直接求解器:CHOLMOD

稀疏直接求解器是计算分析中的基本工具，它提供了一种非常通用的方法来获得几乎所有问题的高质量结果。 CHOLMOD 是用于稀疏 Cholesky factorization 的高性能库.

我保证这个包一定会对你有所帮助。此外，自 2012 年 4.0.0 版以来，CHOLMOD 已支持 GPU 加速。在 SuiteSparse-4.3.1 中，性能得到了进一步改进，与 CPU 相比，稀疏分解运算的速度提高了 3 倍或更高。

如果您的矩阵是图形的表示，您还可以考虑 METIS与 CHOLMOD 的组合。这意味着您将能够在图形中进行分区/域分解，然后使用 CHOLMOD 并行求解。

SuiteSparse 是一个强大的工具，支持线性 (KLU) 和直接求解器。

这是 GitHub link , UserGuide和 SuiteSparse's home page