一种用于复非对称不定线性系统的交替 Anderson–加速拟 SSOR Richardson 方法

《Journal of Computational and Applied Mathematics》：An alternating Anderson–accelerated quasi–SSOR Richardson method for complex nonsymmetric indefinite linear systems

　　

摘要 复非对称不定线性系统出现在许多科学与工程应用中。然而，针对此类问题的高效迭代方法的发展远不及复对称系统。在本文中，我们提出了一种交替 Anderson 加速拟 SSOR-Richardson 方法，称为 A3SRreal 方法，用于求解复非对称不定线性系统。所提出的方法在 Richardson 框架内采用了一种新颖的拟 SSOR 预处理子，以有效利用潜在的问题结构，同时引入 Anderson 加速以进一步改善收敛性。严格的收敛性分析表明，当使用最优参数 ω*=σ*=1 时，A3SRreal 方法无条件收敛。数值实验表明，所提出的方法是高效且鲁棒的，优于几种最先进的求解器，包括 PGSOR、PRESB–GMRES、HSS–GMRES 和 PMHSS–GMRES。此外，详细研究了参数选择的影响以及 Anderson 加速的加速效果。

引言 考虑复值线性系统 Au=b，A∈Cn×n，u,b∈Cn，其中大型稀疏系统矩阵具有如下形式 A=W+iT，其中 W∈Rn×n 是非对称正定矩阵，T∈Rn×n 是对称不定矩阵。此外，当复数运算的计算成本超过其优势时，通常更倾向于将问题重写为如下二乘二实块系统：(W?TTW)︸A(xy)=(pq)，其中 u=x+iy, b=p+iq, (x,y,p,q∈Rn)。例如，这类系统出现在麦克斯韦方程 [1] 和亥姆霍兹方程 [2], [3], [4] 的有限元或有限差分解中，以及信号处理和雷达成像中的复最小二乘问题 [5] 中。

当 W 和 T 均为对称矩阵，且 W 正定、T 半正定时，Bai 等人 [6] 提出了修正的 Hermitian 和斜 Hermitian 分裂 (MHSS) 方法，并在 [7] 中引入了其预处理变体，即 PMHSS 方法。通过将复系统 reformulate 为实值系统，Axelsson 和 Kucherov [8] 提出了一种实值迭代方法及其预处理版本。对于 (1.3)，Salkuyeh 等人 [9] 提出了广义逐次超松弛 (GSOR) 方法，Hezari 等人 [10] 进一步为 GSOR 开发了一种特定的预处理子，从而导出了预处理 GSOR (PGSOR) 方法。

当 W 和 T 均为对称半正定矩阵时，Bai [11] 建立了一种旋转块三角预处理子，Lang 和 Ren [12] 后来提出了一种不精确变体以加速它。Shirilord 和 Dehghan [13] 为这类问题开发了一种单步迭代方法。此外，当 W 是对称不定的且 T 是对称正定的，Zhang 和 Dai [14] 提出了一种新颖的块分裂预处理子，后来 Fan 等人 [15] 对其进行了改进，以更好地近似系统矩阵。最近，针对此类对称不定系统的迭代求解器也在 [16] 中得到了开发。然而，关于求解非对称不定系统的研究仍然有限，这主要是因为非对称性在收敛性分析和算法设计方面都带来了额外的挑战。

Anderson 加速 (AA) 最初由 Anderson [17] 为非线性积分方程引入，已成为定点迭代最有效的加速技术之一。它可以显著改善收敛速度，在某些情况下甚至可以防止发散。在线性系统的背景下，Walker 和 Ni [18] 确立了 AA 与 GMRES 方法之间的基本联系，从而将 AA 置于更广泛的 Krylov 子空间方法类别中。后续的工作扩展了其适用性。Fang 和 Saad [19] 将 AA 纳入拟牛顿框架，Brezinski 等人 [20] 提出了一种基于 Shanks 序列变换的统一观点，其中包含 AA 作为特例。理论理解也有显著进步。Evans 等人 [21] 证明了 AA 改善了收缩定点迭代的收敛性，而后续分析则解决了某些非收缩设置 [22], [23]。

由于每一步 AA 都需要求解一个最小二乘问题，因此它引入了额外的计算成本。为了减少这种开销，Phanisri 等人 [24], [25] 提出了交替 Anderson 加速策略，该策略仅每隔第 s 次迭代应用 AA，已被证明是一种更经济的选择。

最近，一种基于交替 Anderson 加速的通用加速框架，即 PA3R 方法，已在 [26] 中针对线性系统提出。该框架提供了一个统一的视角，将 Anderson 加速与经典分裂迭代方法相结合，并从谱的角度揭示了与 GMRES 等 Krylov 子空间技术的内在联系。由于其灵活性，PA3R 框架可以适应广泛的迭代方案，以增强其收敛行为。

受 PA3R 框架的启发，我们专注于复非对称不定线性系统，并开发了一种专用的迭代求解器，以有效利用其代数结构。具体来说，基于 Richardson 迭代，我们引入了一种新颖的拟 SSOR 型预处理子，并纳入了交替 Anderson 加速策略，从而形成了所提出的 A3SRreal 方法。与通用的 PA3R 框架不同，所提出的方法是专门为复非对称不定系统设计的，从而提高了鲁棒性、效率和可扩展性。

本工作的主要贡献总结如下：1) 为复非对称不定线性系统提出了一种新颖的拟 SSOR-Richardson 迭代框架。2) 将交替 Anderson 加速整合到所提出的框架中，产生了收敛行为显著改善的 A3SRreal 方法。3) 建立了严格的收敛性分析。特别是，理论上证明最优参数为 ω*=σ*=1，从而产生了一个无参数且无条件收敛的方案。4) 在合成和真实世界基准问题上的广泛数值实验表明，所提出的方法始终优于几种最先进的方法，包括 PGSOR、PMHSS-GMRES、HSS-GMRES 和 PRESB-GMRES。

本文其余部分组织如下。第 2 节提出了所提出的 A3SRreal 方法及其收敛性分析。第 3 节报告了数值实验和性能比较。最后，第 4 节得出结论。

记号：令 Rn×n 和 Cn×n 为 n 阶实数和复数方阵集合，Rn=Rn×1, Cn=Cn×1。令 i=?1 为虚数单位。对于 A∈Cn×n，A* 表示其共轭转置，ρ(A) 为其谱半径，diag(A) 和 tridiag(A) 为其对角部分和三对角部分。符号'?'表示 Kronecker 积。

章节片段 SRreal 方法 注意在实值系统 (1.3) 中，A∈R2n×2n 是非奇异的，因为其 Schur 补 S:=W+TW?1T∈Rn×n 是非奇异的 [27]。让我们通过考虑 Richardson 迭代 [28], [29] 来逼近 (1.3)：E(ω)u(k+1)=E(ω)u(k)+σ(b?Au(k))，其中 E(ω) 是一个预处理子，0 < σ ≤ 1 是松弛参数。SSOR 迭代方法的高效性是众所周知的 [30], [31], [32], [33], [34], [35]，其预处理子为 PSSOR=1(2?τ)τ(DA+τLA)DA?1(DA+τUA)，其中 τ > 0 是一个迭代...

数值性能 本节致力于评估方法 2.3 中 A3SRreal 方法的高效率。比较方法 对于复对称正定 (SPD) 系统（例 3.1–3.2），我们将 A3SRreal 方法与 PMHSS [7] 方法、PGSOR [10] 方法（优于 GSOR [9] 和 MHSS [6]）以及带有预处理子的 GMRES 进行比较：PMHSS [7], [39] 和 PRESB [40]（其预处理矩阵的特征值在 [0.5, 1] 内）；对于复非对称不定系统（例 3.3–3.4），我们...

摘要 在本文中，我们提出了一种新的交替 Anderson 加速拟 SSOR Richardson 方法，称为 A3SRreal，用于求解复非对称不定线性系统。所提出的方法将一种新颖的拟 SSOR 型预处理子与交替 Anderson 加速相结合，产生了一种鲁棒且高效的迭代求解器。建立了完整的收敛理论，并从理论上导出了最优参数选择 ω*=σ*=1。在该参数设置下，所提出的方法...

基金 本研究得到了国家重点研发计划 (批准号 2023YFF0804100) 和中央高校基本科研业务费的支持。

竞争利益声明 作者声明他们没有任何已知的竞争财务利益或个人关系，这些关系可能会影响本文中报告的工作。

Zhizhi Li|Huai Zhang|Yuanyuan Yang|Bing Zhang
中国科学院大学地球与行星科学学院地球系统数值模拟与应用重点实验室，北京，100049，中国