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

项目名称： 求解时间依赖问题的隐式时空并行 Schwarz 算法研究

项目编号： No.11726635

项目类型： 专项基金项目

立项/批准年度： 2018

项目学科： 数理科学和化学

项目作者： 蔡小川

作者单位： 中国科学院深圳先进技术研究院

项目金额： 20万元

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

中文关键词： 时空并行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.

英文关键词： space-time Schwarz algorithm;time-dependent problems;Convergence rate;scalability;speedup