基于 HSS 迭代方法的加性 Schwarz 算法

For solving large scale of partial differential equations on complex domain, domain decomposition methods attract many researchers’ interests because of its optimality and good parallel performance. HSS iteration method was proposed recently for solving non-symmetric linear systems, which has perfect convergence theory and good numerical performance. This program is devoted to present a new additive Schwarz algorithms based on HSS iteration method. We will study this new parallel algorithm for solving non-symmetric elliptic equations and linear parabolic equations. By adopting the well-known Schwarz theory, we will prove the convergence of this algorithm and show its scalability and effectiveness by numerical experiments. With the development of supercomputers, space-time domain decomposition method for solving parabolic equation attracts many researchers’ attention. In this program, we also present a new space-time additive Schwarz algorithm, which are parallel on both time and space, and can compute the solutions of many time steps at one time. We will prove the convergence rate and investigate the relationship between the convergence rate and the number of the time steps. In addition, we will show its effectiveness numerically. With the properties of the HSS iteration methods and the advantage of domain decomposition method, the research of these new parallel algorithms is much significance both theoretically and practically.

在求解复杂区域上的大型偏微分方程模型问题中，区域分解方法以其最优的收敛性和高度的可并行性受到许多研究者的青睐。HSS 迭代算法是新近提出的求解非对称线性代数方程组的数值方法，具有完善的收敛理论和良好的计算效果。本项目将基于 HSS 迭代法给出一种新的加性 Schwarz 算法。针对非对称椭圆方程和线性抛物方程，借助经典的 Schwarz 理论分析，研究该并行算法的收敛性，并在数值上验证其可扩展性和有效性。随着超级并行机的发展和问世，求解抛物方程的时空区域分解算法开始被广泛研究，本项目将提出一种新的隐式时空加性 Schwarz 算法，即在时域和空域上同时并行求解，每次计算出多个时间步的解。证明该算法的收敛率并讨论收敛率与时间步数之间的关系，最后在数值上验证该算法的有效性。总之，结合了 HSS 迭代法的特点和区域分解算法的优点，该类并行算法的研究具有重要的理论意义和应用价值。

本项目主要在理论上和数值上研究求解大规模偏微分方程的并行区域分解算法。由于并行计算机特别是超级计算机的快速发展，使得求解科学与工程中的大规模问题成为可能。例如石油勘探和开采、天气预报、航天飞行器的设计、半导体模型设计以及生物医药的研制等问题。因此设计能够快速求解上述问题并且能在并行计算机上运行的并行算法是当前科学计算中的重要研究之一。针对非对称正定椭圆问题，本项目首先研究了基于 AHSS （非对称的埃尔米特/反埃尔米特分裂）迭代法的加性 Schwarz 算法。在理论上给出了最优收敛性分析，并给出了算法中两个参数的选取方法，即与离散线性方程组系数矩阵的对阵正定部分的最大和最小特征值相关。最后给出了数值实验验证了算法的最优性，并给出了与经典的加性 Schwarz 算法的数值比较结果，数值比较表明我们的算法对于求解对流占优的对流扩散问题具有更好的数值结果。针对抛物问题，传统的数值方法只能是一个时间步接着一个时间步的顺序求解，即只在空间上并行而在时间上串行。本项目主要研究了一种时空并行的加性 Schearz 算法。即在空间和时间上分别采用有限元和有限差分方法离散并得到一个由多个时间步问题耦合的线性系统，然后用两层加性 Schwarz 算子作为 Krylov 子空间方法的预条件子求解该线性系统。在一定条件假设下，我们证明了两层时空加性 Schearz 算法具有最优收敛性，即其收敛率与细网格步长、时间步长、子区域个数和耦合时间步数无关。通过大量的数值实验也验证了上述理论结果。无论在理论上还是在数值上该时空并行算法都得到了与传统加性 Schearz 算法求解椭圆方程类似结果。该结果已发表在国际期刊 SIAM on Numerical Analysis上。此外，为了能够使该算法具有更好的实用性，我们还将其推广到多层情况上，该部分工作正在整理之中，其中收敛性理论已经证明。数值上我们成功地在超级计算机天河 2 号实现该类算法，并扩展到数千核上。总之，该项目不但圆满完成了任务，也为下一步工作打下了基础。