预处理 GMRES 和 MINRES 的性能差异

计算科学 线性代数 数值分析
2021-12-24 02:07:50

我有两个矩阵A,B来自偏微分方程系统的有限元离散化。A表示系统矩阵,是对称且不定的。B是对称正定的,用作预条件子。直接求解器用于计算B1. 前置机还不错σ(B1A)(10,0.1)(0.1,10).

当我使用 GMRES 解决这个系统时B经过合理数量的迭代后,我得到了近似解。然而,在 MINRES 中使用相同的预处理器时会失败。预处理系统的迭代次数甚至高于未预处理系统。(我使用 PETSc、Matlab 和 scipy 尝试了这种计算,得到了相同的定性结果。)

您能否将我导航到一些理论结果或可以解释这种行为的关键字?

编辑:我在我的代码中发现了一个错误,问题不再有效,B(稍微)不对称,这使得 MINRES 无用。我深表歉意。

2个回答

您是否将 MINRES 应用于操作员B1A? 除非BA通勤,这不太可能,产品B1A不是对称的。我猜这就是您的情况发生的情况,因为即使对于非对称矩阵也适用的 GMRES 确实收敛了,而 MINRES 则没有。

您提到使用直接因式分解B. 如果您使用 Cholesky 分解B=LL, 那么矩阵L1AL是对称的。如果你将 MINRES 应用到这个系统中,你可能会有更好的运气。

预处理系统比原始系统需要更多的迭代,这有点奇怪。但是,所有非对称迭代方法都有奇怪的失效模式,并且可以在某些输入矩阵上缓慢收敛。有关示例,请参见本文在任何情况下,您都提到了使用 PETSc,因此您可以随时尝试其他预处理器,看看哪种效果最好。

使用预调节器B用于解决系统Ax=b对应解决系统B1Ax=B1b,因为,正如丹尼尔所指出的,B1A一般是不对称的。相反,它对应于解决

B1/2AB1/2x~=B1/2b.
你也可以正式考虑系统
B1Ax=B1b
并使用内积,B, 或系统
AB1x~=B1b
并使用内积,B1. 所有三个观点都将导致完全相同的算法,即预处理的 MINRES。(与CG相同,顺便说一句。)

请注意,所有三个系统的频谱都相同,

σ(B1/2AB1/2)=σ(B1A)=σ(AB1),
所以看着σ(B1A)没关系。

至于为什么 MINRES 和 GMRES 在收敛行为上不同,很难说。也许你犯了一个错误,将 MINRES 应用于B1A. 如果不是,另一种解释可能是 MINRES 中正交性的丧失。请注意,对于精确算术中的对称矩阵,MINRES 和 GMRES完全相同不同之处在于 GMRES 保留了 Krylov 空间的基础来进行正交化,而 MINRES 依赖于某些属性仅对最后几个向量进行正交化。这可能容易出错。由于这两种算法做的事情完全相同,所以有人说

GMRES 是最强大的 MINRES 实施。

如果你不缺内存,GMRES 肯定可以安全使用。