多层时空并行 Schwarz 算法的研究

Parallel algorithm for solving large-scale partial differential equations has become very important with the development of the supercomputer. Domain decomposition method has been investigated by many researchers because it is optimal and easy for parallelization. This program is devoted to present new implicit space-time Schwarz algorithms for solving parabolic equations, i.e., the finite difference method and finite element method are used to discretize the time and space domain. Then solve the coupled system by using multilevel Schwarz algorithms and obtain the solutions at many time steps. Firstly, based on the multistep method, we present multilevel space-time additive and multiplicative Schwarz algorithms. Then, by establishing two important properties of the space and time decomposition, i.e., a strengthened Cauchy-Schwarz type inequality and a stable multilevel decomposition, we develop a convergence theory and show how the convergence rate depends on the mesh sizes, the number of subdoamins, the window size and the umber of levels. Finally, some numerical experiments implemented on a parallel computer with thousands processors are presented and confirm the theory in terms of the optimality and scalability. The study of these new parallel algorithms is much significant for solving long time-dependent problems on both theoretically and practically.

随着并行机的发展，并行算法求解大规模偏微分方程问题已成为科学计算中的重要研究方向之一。区域分解算法以其最优的收敛性和高度的可并行性受到众多研究者的青睐。本项目将提出一类求解抛物方程的时空并行 Schwarz 算法，即在时域上和空间上分别采用有限差分方法和有限元方法离散，得到一个耦合的线性系统，利用多层 Schwarz 算法在并行机上求解并得到多个时间步的解。首先，在时域上采用线性多步方法，提出求解抛物方程的时空并行的多层加性和乘性 Schwarz 算法。然后，通过建立关于时空区域分解的强 Cauchy-Schwarz 不等式性质和稳定分裂性质，证明该类算法的最优收敛性，分析其收敛率与网格步长、子区域个数、耦合的时间步数和网格层数之间的关系。最后，通过数值实验说明该类算法的最优性，并给出其在数千个核上的可扩展性结果。该类并行算法的研究对于快速求解长时间依赖问题具有重要的理论意义和应用价值。

近年来，随着并行计算机的快速发展，使得快速高效地计算模拟实际工程中的大规模问题成为可能。因此研究和设计适合高性能计算机的并行算法也是非常必要的。本项目主要研究了求解抛物方程的多层时空并行 Schwarz 算法。即在时间上用有限差分方法离散，在空间上用有限元离散原问题，将多个时间步问题耦合成一个大的问题并用多层 Schwarz 算法并行求解。通过建立关于时空区域分解的强 Cauchy-Schwarz 不等式性质和稳定分裂性质，我们证明了该算法是最优收敛的，即在一定假设条件下，算法的收敛率与网格步长、子区域个数、耦合的时间步数和网格层数是无关的。另外我们基于PETSc 软件包成功地在天河二号超级计算机上得到了该算法求解三维抛物方程的数值结果。结果表明该算法具有很好的强可扩展性和弱可扩展性。与传统的时间串行算法比较可以发现时空并行算法具有计算时间短、并行效率高等特点。相关成果发表在国际 SCI 期刊 《SIAM Journal on Scientific Computing》上。 此外，针对多层时空乘性 Schwarz 算法的研究在理论上也取得了最优收敛性结果。总之，该类时空并行算法在求解线性抛物方程取得了很好的理论和数值结果，为进一步研究其它时间相关问题做好了铺垫。