用另一种 Krylov 方法对 Krylov 方法进行预处理

计算科学 线性代数 线性求解器 预处理 克雷洛夫法 格瑞斯
2021-12-07 23:06:56

在 gmres 或 bicgstab 等方法中,使用另一种 Krylov 方法作为预处理器可能很有吸引力。毕竟,它们很容易以无矩阵方式和并行环境实现。例如,可以使用几次(比如说约 5 次)未预处理的 bigcstab 迭代作为 gmres 的预连接器,或 Krylov 方法的任何其他组合。

我在文献中没有找到太多关于这种方法的参考,所以我认为这是因为它不是很有效。我想了解为什么它没有效率。在某些情况下它是一个不错的选择吗?

在我的研究中,我对并行 (MPI) 环境中 3-D 椭圆问题的解决方案感兴趣。

2个回答

有趣的是,这个问题是昨天出现的,因为我昨天刚刚完成了一个执行此操作的实现。

我的背景

首先,让我知道,虽然我的教育背景来自科学计算,但我毕业后所做的所有工作,包括我目前的博士学位。工作,一直在计算电磁学。所以,我想我们的背景有些相似,因为你似乎也在研究物理学(根据你的个人资料)。

割礼

首先,正如 Guido Kanschat 在评论中已经提到的那样,您正在寻找的是灵活的 GMRES 或 FGMRES。参考资料(包括伪代码)在 [1] 中。虽然我有时会发现数字 SIAM 论文有点难以阅读,但 [1](以及 Saad 的大部分其他作品,包括出色的 [B1],显然在网上合法免费提供)是不同的;这篇论文读起来很吸引人,写得非常清楚,并有一些很好的例子和应用建议。

FGMRES 很容易实施,特别是如果您已经有一个可工作的 RIGHT 预处理 GMRES。请注意此处的关键字 RIGHT - 如果您有一个 LEFT 预处理 GMRES,即您习惯于求解 MAx=Mb,那么您必须进行一些修改。比较 [B1,算法 9.4 在 pg。282] 到 [B1,算法 9.5,pg。284]。您还可以在 [B1,Algorithm 9.6, pg. 中找到 FGMRES。287],但我真的鼓励您阅读 [1],因为它很短,写得很好,并且仍然有许多有趣的细节。

它有什么作用

如果您愿意,FGMRES 基本上允许您为每次迭代切换预处理器。其中一个应用是,您可以使用一些在远离解决方案时效果很好的预处理器,然后在您靠近时切换到另一个。[2],我没有详细阅读,似乎讨论了类似的事情。

但是,在我的案例中,最有趣的应用是您可以使用(预处理的)GMRES 作为 FGMRES 的预处理器。这就是 FGMRES 的典型名称“内外 GMRES”背后的原因。这里,“外部”是指 FGMRES 求解器,它(作为预处理器)使用“内部”求解器。

那么,这在实践中有多好?

就我而言,这非常出色。在内部循环中,我“解决”了我的问题的降低复杂度的公式。就其本身而言,这个解决方案对于我们的使用来说太不准确了,但它作为一个预处理器绝对有用。请注意“求解”周围的“” - 无需运行内部求解器来收敛,因为您只是在寻找粗略的近似值。在我的例子中,我从使用 151 次迭代,每次花费 64 秒,到 72 次迭代,每次花费 79 秒(我在内部 GMRES 中使用了固定的 5 次迭代)。这总共节省了一个小时,没有损失准确性,而且编码工作也很少,因为我们已经有了一个功能正常的 GMRES,我们只是将其递归。

对于这个东西的一些应用,展示潜在的性能,见[3](它实际上使用了一个三级FGMRES,所以FGMRES,FGMRES作为内部,GMRES作为内部内部)和[4],这可能也是特定于您使用的应用程序,但包含几个有趣的测试用例。

参考

[1] Y. Saad,“一种灵活的内外预条件 GMRES 算法”,SIAM J. Sci。比较,卷。14,没有。2,第 461-469 页,1993 年 3 月。http: //www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf

[2] D.-Z。丁,R.-S。Chen 和 Z. Fan,“SSOR 预处理内外柔性 GMRES 方法用于 MLFMM 开放物体散射分析”,电磁学研究进展,卷。89,第 339-357 页,2009 年。http: //www.jpier.org/PIER/pier89/22.08112601.pdf

[3] TF Eibert,“通过多级快速多极方法加速的表面积分方程和混合有限元边界积分技术计算的一些散射结果”,IEEE 天线和传播杂志,第一卷。49,没有。2,第 61-69 页,2007 年。

[4] 奥。Ergül、T. Malas 和 L. Gürel,“使用具有普通和近似多级快速多极算法的迭代内外方案解决大规模电磁学问题”,电磁学研究进展,卷。106,第 203-223 页,2010 年。http: //www.jpier.org/PIER/pier106/13.10061711.pdf

[B1] Y. Saad,稀疏线性系统的迭代方法。暹罗,2003。http ://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf

这种嵌套的 Krylov 子空间方法在实践中可能工作得很好。对于重新启动的 GMRES 停滞且未重新启动的 GMRES 太昂贵或使用太多内存的非对称线性系统可能会感兴趣。一些文献:

  1. GMRESR:一系列嵌套的 GMRES 方法,van der Vorst,Vuik
  2. 灵活的内外 Krylov 子空间方法,Simoncini,Szyld
  3. 一种灵活的内外预条件GMRES算法
  4. 进一步体验 GRESR , Vuik