什麼是大拉普拉斯矩陣的快速簡單求解器？

Question

我需要解決電阻網絡研究中出現的一些大的（N〜1e6）拉普拉斯矩陣。網絡分析的其餘部分正在使用boost圖處理，如果可能的話，我想留在C++中。我知道有很多很多C++矩陣庫，但似乎沒有人在速度或可用性方面明顯領先。另外，關於這個主題的許多問題，這裏和其他地方似乎都迅速轉化爲效用有限的洗衣清單。爲了幫助自己和他人，我會盡量保持問題的簡明性和可回答性：

什麼是可以有效處理以下要求的最佳庫？

• 矩陣類型：對稱角佔優/拉普拉斯
• 尺寸：非常大（N〜1E6），無動態調整所需
• 稀疏：極限（每行的最大5非零項/列）
• 需要的操作：求解A * x = b和mat/vec中的x
• 語言：C++（C ok）
• 優先級：代碼的速度和簡單性。我真的寧願避免爲這個問題學習一個全新的框架，或者不得不手動編寫太多的幫助代碼。

超愛用最少的工作示例答案...

Answer 1

有很多相關的帖子，你可以有外觀。 我會建議C++和boost :: uBLAS庫爲UMFPACK and BOOST's uBLAS Sparse Matrix

Answer 2

徵使用的是相當不錯的使用和最快的圖書館之一，我知道：

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

Answer 3

如果你想編寫自己的求解，就簡單性而言，很難擊敗Gauss-Seidel迭代。更新步驟是一行，並且可以很容易地進行並行化。 （SOR）只是稍微複雜一些，收斂速度要快得多。

Conjugate gradient對於代碼也很簡單，並且應該比其他迭代方法更快地收斂。重要的是要注意的是，你不需要形成完整的矩陣A，只需計算矩陣向量積A * b。一旦工作完成，您可以通過添加預處理器（如SSOR（對稱SOR））來再次提高會聚率。

可能是自己編寫合理的最快解決方法是基於傅里葉的解算器。它主要包括對右側進行FFT，將每個值乘以其座標的函數，並進行逆FFT。您可以使用一個FFT庫，如FFTW，或者自己推出。

Arieh Iserles提供的所有這些內容都是A First Course in the Numerical Analysis of Differential Equations。