algorithm - 边值问题的快速算法

Question

我正在寻找解决以下问题的最快方法:

给定 3D 网格中的一些格点体积，一些点 b_i(边界)满足 f(b_i)=0，而另一个点 a_0 满足 f(a_0)= 1。

所有其他点(非边界)都是周围 26 个点的某种线性组合。例如，我可能想要

f(i, j, k)= .05*f(i+1, j, k)+.1*f(i, j+1, k)+.07*f(i, j, k+1)+...

系数 .05+.1+.07+... 的总和将加起来为 1。我的目标是为卷中的所有 x_i 求解 f(x_i)。

目前，我正在使用连续过度松弛(SOR)方法，它基本上是初始化体积的边界，为每个点分配周围 26 个点的加权平均值，然后重复。 SOR 方法仅采用最近一次迭代后的 f(x_i) 和之前迭代后的 f(x_i) 的组合。

我想知道是否有人知道任何更快的方法来解决大小为 102x102x48 的 3D 网格的这个问题。 SOR 目前需要大约 500-1000 次迭代才能收敛到我想要的水平(根据使用的系数而有所不同)。我最愿意用matlab、idl、c++。有谁知道 SOR 与将问题转换为线性系统并使用矩阵方法(如 BCGSTAB)相比有多快？另外，哪种方法最有效(也最容易)并行化？我可以访问一个 250 核心的集群，并且一直在尝试使用 mpi 和 c++ 使 SOR 方法并行，但没有看到我想要的速度增加(理想情况下是 100 倍左右)。对于加快解决此问题的任何想法，我将不胜感激。谢谢。

Answer 1

如果您熟悉多线程，对 SOR 使用红黑方案可以提供不错的加速。对于二维问题，想象一个棋盘 - 红色方 block 仅依赖于黑色方 block (可能还有它们自身)，因此您可以并行更新所有红色方 block ，然后对所有黑色方 block 重复。请注意，这确实比简单排序收敛得更慢，但它可以让您将工作分散到多个线程上。

共轭梯度法通常会比 SOR 收敛得更快(如果我没记错的话，大约快一个数量级)。我从未使用过 BCGSTAB，但我记得 GMRES 在处理非对称问题时效果很好，它们可能都可以从预处理中获益。

至于并行化的机会，大多数 CG 类型的方法只需要您计算矩阵向量乘积 A*x，因此您永远不需要形成完整的矩阵。这可能是每次迭代的最大成本，因此您应该关注多线程。

两个很好的引用资料是 Golub and Van Loan , 和 Trefethen and Bau .恕我直言，后者更具可读性。

希望对您有所帮助...