4

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

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

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

非常喜欢用一个最小的工作示例来回答......

4

3 回答 3

4

如果您想编写自己的求解器，就简单性而言，很难击败Gauss-Seidel迭代。更新步骤是一行，并且可以很容易地并行化。连续过度松弛(SOR) 只是稍微复杂一些，收敛速度更快。

共轭梯度也很容易编码，并且应该比其他迭代方法收敛得更快。需要注意的重要一点是，您不需要形成完整的矩阵 A，只需计算矩阵向量乘积 A*b。一旦它起作用，您可以通过添加像 SSOR（对称 SOR）这样的预处理器来再次提高收敛率。

可能最适合自己编写的求解方法是基于傅立叶的求解器。它本质上涉及取右侧的 FFT，将每个值乘以其坐标的函数，然后取逆 FFT。您可以使用FFTW 之类的 FFT 库，也可以使用自己的库。

所有这些的一个很好的参考是Arieh Iserles的微分方程数值分析第一课。

于 2013-07-01T15:18:48.500 回答
2

Eigen 非常好用，也是我所知道的最快的库之一：

http://eigen.tuxfamily.org/dox/group__TutorialSparse.html

于 2013-07-01T11:10:29.260 回答
0

有很多相关的帖子，你可以看看。我会推荐UMFPACK 和 BOOST 的 uBLAS 稀疏矩阵中使用的 C++ 和 Boost::ublas

于 2013-07-01T09:57:08.070 回答