我正在寻找最快的方法来解决以下问题:
给定三维网格中的一些点阵点的体积,一些点阵点(边界)满足b_i,而另一个点阵点满足f(b_i)=0
所有其他点(非边界)都是周围26个点的线性组合。例如,我可以

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

系数之和a_0等于f(a_0)= 1。我的目标是解决体积中所有.05+.1+.07+...1
目前,我正在使用逐次过松弛(sor)方法,它基本上初始化体积的边界,为每个点指定26个周围点的加权平均值,然后重复。SOR方法只是在最近一次迭代之后取f(x_i)和之前一次迭代之后取x_i的组合。
我想知道是否有人知道任何更快的方法来解决这个问题的三维网格大小为102x102x48SOR目前需要大约500-1000次迭代才能收敛到我想要的水平(根据使用的系数而变化)我非常愿意使用matlab、idl和c++有人知道SOR与将问题转化为线性系统和使用矩阵方法(如BCGSTAB)相比有多快吗另外,哪种方法最有效(也最容易)并行化我已经访问了一个250核的集群,并且一直在尝试使用mpi和c++使sor方法并行,但是没有看到像我所希望的那样多的速度增长(理想的速度是100倍)。如果你能提出任何加快解决这个问题的办法,我将不胜感激。谢谢。

最佳答案

如果您对多线程很熟悉,那么对sor使用红黑方案可以提供相当不错的加速。对于一个二维问题,想象一个棋盘格-红色方块只依赖于黑色方块(可能还有它们自己),所以你可以平行地更新所有的红色方块,然后对所有的黑色方块重复。注意,这确实比简单的排序收敛得慢,但它允许您将工作分散到多个线程上。
共轭梯度法通常比sor收敛得快(如果我没记错的话,大约一个数量级)。我从未使用过BCGSTAB,但我记得GMRES在非对称问题上工作得很好,它们可能都能从预处理中受益。
至于并行化的机会,大多数cg类型的方法只需要计算矩阵向量积,因此不需要形成完整的矩阵。这可能是每次迭代的最大成本,因此应该考虑多线程。
两个很好的参考文献是Golub and Van LoanTrefethen and Bau。后者更具可读性。
希望能帮上忙。。。

09-11 17:28