如何求解非常大的系统的稀疏线性系统

Question

我正在尝试用c++解决一个非常大且稀疏的线性方程组。目前，我正在使用来自eigen的bicstab。对于小矩阵它工作得很好，但是对于我需要的大小的矩阵，它花费了太多的时间，这是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分解的高性能库。

我保证这个包一定会帮到你。此外，CHOLMOD从2012年的4.0.0版本开始支持GPU加速。在SuiteSparse-4.3.1中，性能得到了进一步的改进，与CPU相比，稀疏分解操作的速度提高了3倍或更高。

如果你的矩阵是图的表示，你也可以考虑结合CHOLMOD的METIS。这意味着您将能够在图中进行分区/domainDecomposition，然后与CHOLMOD并行求解。

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

这里是GitHub链接，UserGuide和SuiteSparse的主页