求解时间依赖问题的隐式时空并行 Schwarz 算法研究

Time-parallel algorithms can solve time-dependent problems quickly and improve parallel efficiency of the supercomputer greatly. This program is devoted to study some implicit space-time Domain Decomposition Methods for solving time-dependent problems, i.e., we solve the problems in parallel on both time and space by using multilevel Schwarz algorithms. Unfortunately, the existing theory for Schwarz algorithms does not apply directly to the space-time discretized problem. In this program, we develop an optimal convergence theory for the multilevel space-time additive and multiplicative Schwarz algorithms applied to parabolic equations, and show how the convergence rate depends on the mesh sizes, the number of subdoamins, the window size and the number of levels. To improve the accuracy of the solution, we also study some space-time Schwarz algorithms with high-order schemes used in the time direction, such as multistep difference formula, Runge-Kutta and Crank-Nicolson schemes. Finally, some numerical experiments carried out on a parallel computer with thousands of processors confirm the theory in terms of the number of iterations, as well as the strong and weak scalability. This program will provide the theoretical foundation for these multilevel space-time Schwarz algorithms applied to more practical problems.

时间并行算法不仅能快速求解时间依赖问题的解，而且能极大地提高并行计算机的效率。本项目将研究一类求解时间依赖问题的隐式时空并行区域分解算法，即在空间区域上和时域上利用多层 Schwarz 算法同时并行求解原问题。由于经典的 Schwarz 理论仅适用于空间并行算法而不适用于时空并行算法。本项目首先以抛物方程为模型，给出多层时空加性和乘性 Schwarz 算法的最优收敛性分析，研究其收敛率与网格步长、子区域个数、耦合时间步数和网格层数之间的关系。为了提高解的精确度，本项目将进一步研究时域上采用线性多步法、龙格-库塔和 Crank-Nicolson 等高阶离散格式的时空并行 Schwarz 算法。最后，在数值实验上，通过算法的迭代步数以及在数万核上的强/弱可扩展性结果验证最优收敛性和并行性。本项目的研究不仅构造了一类高效实用的时空并行算法，也为其应用到更加实际问题提供了理论基础和支撑。

近十年来超级计算机的核数增长迅速。能够设计出满足高并行度的有效并行算法是在目前是一项具有挑战性的工作，特别是对于求解时间依赖问题。为了提高并行度和超级计算机的利用效率，很多时间并行算法被提出和研究。本项目我们主要提出和研究了多层时空并行 Schwarz 算法求解抛物方程。在一定条件假设下，我们证明了算法的收敛性仅仅与每层网格上子区域大小和重叠区域大小的比例有关，而与网格步长、子区域个数、耦合的时间步数和网格层数没有关系。数值实验证明了算法的最优收敛性. 通过在天河二号超级计算机数千核上的测试结果表明时空并行 Schwarz 算法具有很好的强可扩展性和弱可扩展性。进一步，通过在四维时空网格上求解三维抛物方程的的数值结果，我们发现当计算机核数很大时，时空加性 Schwarz 算法比传统的只在空间上并行的时间串行算法更有优势。部分结果发表在国际 SCI 期刊《SIAM Journal on Scientific Computing》上。下一步工作我们将继续研究该算法求解其他时间依赖问题。