什么是大型拉普拉斯矩阵的快速简单求解器? [英] What is a fast simple solver for a large Laplacian matrix?

问题描述

我需要解决在电阻器网络研究中出现的一些大(N〜1e6)拉普拉斯矩阵.其余的网络分析将通过boost图进行处理，如果可能的话，我希望继续使用C ++.我知道有很多C ++矩阵库，但是似乎没有人在速度或可用性方面明显领先.而且，关于此主题的许多问题，无论在这里还是在其他地方，似乎都迅速演变为实用性有限的洗衣清单.为了帮助自己和他人，我将尽量使问题简洁明了且易于回答:

I need to solve some large (N~1e6) Laplacian matrices that arise in the study of resistor networks. The rest of the network analysis is being handled with boost graph and I would like to stay in C++ if possible. I know there are lots and lots of C++ matrix libraries but no one seems to be a clear leader in speed or usability. Also, the many questions on the subject, here and elsewhere seem to rapidly devolve into laundry lists which are of limited utility. In an attempt to help myself and others, I will try to keep the question concise and answerable:

什么是可以有效满足以下要求的最佳库?

What is the best library that can effectively handle the following requirements?

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

通过一个最小的工作示例，非常喜欢答案...

Extra love to answers with a minimal working example...

推荐答案

如果要编写自己的求解器，就简单性而言，很难击败成功的过度松弛(SOR)稍微复杂一点，收敛速度更快.

If you want to write your own solver, in terms of simplicity, it's hard to beat Gauss-Seidel iteration. The update step is one line, and it can be parallelized easily. Successive over-relaxation (SOR) is only slightly more complicated and converges much faster.

共轭梯度也很容易编写代码，并且收敛速度要比其他迭代更快方法.需要注意的重要一点是，您无需形成完整的矩阵A，只需计算矩阵向量乘积A * b.一旦成功，您可以通过添加诸如SSOR(对称SOR)之类的前置条件来再次提高收敛速度.

Conjugate gradient is also straightforward to code, and should converge much faster than the other iterative methods. The important thing to note is that you don't need to form the full matrix A, just compute matrix-vector products A*b. Once that's working, you can improve the convergance rate again by adding a preconditioner like SSOR (Symmetric SOR).

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

Probably the fastest solution method that's reasonable to write yourself is a Fourier-based solver. It essentially involves taking an FFT of the right-hand side, multiplying each value by a function of its coordinate, and taking the inverse FFT. You can use an FFT library like FFTW, or roll your own.

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

A good reference for all of these is A First Course in the Numerical Analysis of Differential Equations by Arieh Iserles.

这篇关于什么是大型拉普拉斯矩阵的快速简单求解器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！