2

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

给定 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。我的目标是解决卷中f(x_i)的所有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 倍）。对于加快解决此问题的任何想法，我将不胜感激。谢谢。

4

2 回答 2

3

如果您对多线程感到满意，则对 SOR 使用红黑方案可以提供不错的加速。对于 2D 问题，想象一个棋盘 - 红色方块仅取决于黑色方块（可能还有它们自己），因此您可以并行更新所有红色方块，然后对所有黑色方块重复。请注意，这确实比简单排序收敛得更慢，但它可以让您将工作分散到多个线程上。

共轭梯度法的收敛速度通常比 SOR 快（如果我没记错的话，大约是一个数量级）。我从未使用过 BCGSTAB，但我记得 GMRES 在非对称问题上工作得很好，而且它们可能都可以从预处理中受益。

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

关于这方面的两个很好的参考是Golub 和 Van Loan，以及Trefethen 和 Bau。后者更具可读性恕我直言。

希望有帮助...

于 2011-07-08T06:40:01.760 回答
2

我有（我认为）一个确切的解决方案，但是，它可能很长。主要问题是在一个非常大（并且希望是稀疏的）矩阵上进行计算。

假设N您的卷中有积分。让我们称之为p1...pN这些点。你正在寻找的是f(p1)...f(pN)

让我们说一点pi。它有26个邻居。让我们打电话给他们pi-1...pi-26。我想您可以访问每个点pi的线性组合系数。让我们称它们为（“点到其第 j 个邻居ci-1...ci-j...ci-26的线性组合的系数）pi

让我们做得更好，你可以认为这是你空间中所有pi点的线性组合，除了它们中的大多数（26 个除外）等于 0。你有你的 coefficients 。ci-1...ci-N

您现在可以构建N*N这些ci-j系数的大矩阵：

+---------------------    -------+   
|  0  | c1-2 | c1-3 | ... | c1-N |   |f(p1)|    |f(p1)|
+---------------------    -------+   |     |    |     |
| c2_1|   0  | c2-3 | ... | c1-N |   |f(p2)|    |f(p2)|
+---------------------    -------+ * .     . =  .     .
|                                |   .     .    .     .
.                                .   .     .    .     .
+---------------------    -------+   .     .    .     .
| cN-1| cN-2 | cN-3 | ... |   0  |   |f(pN)|    |f(pN)|
+---------------------    -------+

惊人！您正在寻找的解决方案是对应于特征值 1 的特征向量之一！

使用一个优化的矩阵库来有效地计算特征向量（对于稀疏矩阵），并希望它已经被并行化了！

编辑：有趣，我刚刚重读了你的帖子，似乎我刚刚给了你你的 BCGSTAB 解决方案......对不起！^^

重新编辑：其实我也不确定，你说的是“Biconjugate Gradient Stabilized Method”吗？因为如果你正在做梯度下降，我看不到你所说的线性方法......

重新编辑：我喜欢数学 =) 我什至可以证明给定sum of the ci = 11 实际上是特征值的条件。我不知道对应空间的维度，但至少是1！

于 2011-07-07T14:35:48.637 回答