就解决问题的性能而言，哪种算法更实际适用方程，其中是一个通用的拉普拉斯矩阵（与一个强连通图相关联，它的第一个特征值在大多数情况下为空）。每行可以有超过 100 万行和少于 15 个非空条目。
在我的具体情况下，我尝试使用 C++ 和 Eigen 库作为一个小例子。看到大多数数值求解器库都倾向于提供共轭梯度和 Cholesky 方法，我仍然需要关于这种稀疏求解器的优缺点的更有教育意义的建议。就我的经验而言，CG 应该会更好，但我怀疑问题的规模最终可能会让人不知所措。
求解大稀疏拉普拉斯矩阵的 Lx = b
计算科学
线性求解器
稀疏矩阵
图书馆
2021-12-13 07:14:08
2个回答
Daniel Shapero 的回答非常好，但我觉得我应该添加以下内容：
除非您的系统具有非常非常特殊的结构，否则经过适当预处理的迭代方法几乎肯定会在这里获胜。
最近有大量关于图拉普拉斯系统求解器的文献，不幸的是，大部分都是“运行时间的渐近先验界限”种类。有关论文的参考，请参阅Dan Spielman 的页面。
Spielman 的页面建议使用代数多重网格方法，特别是Oren Livne 和 Achi Brandt 的 LAMG在实践中求解拉普拉斯系统。由于它已经实现了，而且最近许多带有可证明的运行时间界限的拉普拉斯求解器都没有，我建议试一试。
当您尝试使用 Eigen 时，哪个更快？如果你使用 C++，你也可以考虑Trilinos 。
“通用拉普拉斯矩阵”是指拉普拉斯算子在某个域上的有限差分/有限元离散化，还是指某个图的拉普拉斯算子?
当您扩大未知数的数量时，您的求解器是否不堪重负很大程度上取决于基础矩阵。例如，如果是一个带矩阵，然后像 Cholesky 这样的直接求解方法不需要比原始矩阵开始时占用更多的空间。另一方面，如果矩阵的结构不太规则——例如，它来自 2D 中的 5 点模板或随机图形——那么矩阵分解将有很多填充，而 CG 变得更可取。根据我自己的经验，后一种情况更为常见。一般来说，对于二维或更多维度的 PDE，直接方法对于未知数少于 ~ 25,000 个的问题更快，之后迭代方法是明显的赢家。
在任何一种情况下，通过置换矩阵以减少其带宽都会有很多好处。对于直接求解方法，这减少了填充量；对于迭代求解方法，它可以在访问元素时增强参考的局部性.
最后，对于迭代方法，选择一个好的预条件子与选择一个好的求解器一样重要，如果不是更重要的话。Trilinos 和PETSc都有多重网格预处理器的实现，您的问题是教科书应用程序。