c++ - 什么是大型拉普拉斯矩阵的快速简单求解器？

Question

我需要求解电阻网络研究中出现的一些大型 (N~1e6) 拉普拉斯矩阵。其余的网络分析正在使用 boost graph 处理，如果可能的话我想留在 C++ 中。我知道有很多很多 C++ 矩阵库，但似乎没有一个在速度或可用性方面明显领先。此外，这里和其他地方关于这个主题的许多问题似乎很快就变成了实用性有限的洗衣 list 。为了帮助自己和他人，我将尽量使问题简洁明了:

可以有效处理以下要求的最佳库是什么？

• 矩阵类型:对称对角线占优/拉普拉斯
• 大小:非常大 (N~1e6)，不需要动态调整大小
• 稀疏性:极端(每行/列最多 5 个非零项)
• 需要的操作:求解 A*x=b 中的 x 和 mat/vec 相乘
• 语言:C++(C 还行)
• 优先级:编码的速度和简单性。我真的宁愿避免为这个问题学习一个全新的框架，或者不得不手动编写太多的帮助代码。

特别喜欢用最小的工作示例来回答...

Answer 1

如果您想编写自己的求解器，就简单性而言，很难击败 Gauss-Seidel迭代。更新步骤是一行，很容易并行化。 Successive over-relaxation (SOR) 只是稍微复杂一点，收敛得更快。

Conjugate gradient代码也很简单，并且应该比其他迭代方法收敛得更快。需要注意的重要一点是您不需要形成完整的矩阵 A，只需计算矩阵 vector 乘积 A*b。一旦成功，您可以通过添加 SSOR(对称 SOR)等预条件子再次提高收敛率。

您自己编写的合理的最快求解方法可能是基于傅立叶的求解器。它本质上涉及对右侧进行 FFT，将每个值乘以其坐标的函数，然后进行逆 FFT。您可以使用像 FFTW 这样的 FFT 库，或推出您自己的。

所有这些的一个很好的引用是 A First Course in the Numerical Analysis of Differential Equations作者 Arieh Iserles。