基于优化Schwarz算法的非线性预条件问题

With the explosive increase in computing power afforded by parallel computing clusters, parallel solvers for partial differential equations (PDEs) have become an indispensable tool in the simulation of complex, nonlinear phenomena, ranging from material science, chemistry and biology, to the environmental sciences, weather forecasting, petroleum engineering and aeronautics. Domain decomposition (DD) is one of the most widely used classes of parallel numerical algorithms, owing to its relatively simple implementation. Despite the fact that practical problems of interest are generally nonlinear, most DD methods are designed and analyzed with linear problems in mind. Currently, the most common way of solving nonlinear discretized PDEs is to use a classical Newton’s method as the outer loop, and DD is only used to solve the inner, linearized problems in parallel. The main disadvantage of this approach is that Newton’s method may not converge if strong local nonlinearities exist. Truly nonlinear DD methods, such as nonlinear Schwarz methods, are ideally suited for dealing with such local nonlinearities, but they are not widely used because they only converge linearly, unlike Newton’s method, which converges quadratically. About a decade ago, Cai and Keyes invented a nonlinearly preconditioned DD method known as the ASPIN iteration, which solves nonlinear problems locally like nonlinear Schwarz, but which also converges quadratically in the neighbourhood of the solution. Despite these advantages, the local problems are solved using Dirichlet transmission conditions, which are known to be inefficient when the mesh size h is small. Thus, we propose in this project to incorporate optimized transmission conditions of the Robin type into the local solve, leading to much faster convergence rates. We also propose a two-level variant based on the Full Approximation Scheme, which is widely used in multigrid methods, to ensure the scalability of the method. Thus, our first goal is to design a robust, efficient and scalable method for the parallel solution of nonlinear elliptic PDEs, and to establish convergence estimates for our algorithms as a function of parameters such as mesh size, PDE coefficients and the number of the subdomains present. We will analyze the theoretical convergence rate of the new methods and demonstrate the efficacy of our approach using a variety of nonlinear elliptic test problems. Since the choice of Robin parameters in the transmission conditions has a large influence on the convergence rate, we propose to study the problem of choosing the best Robin conditions for a given discretized PDE problem. This study culminates in our second goal, which is to provide heuristic guidelines for choosing Robin parameters based on the problem specifications. This would provide a valuable resource for practitioners who wish to use optimized Schwarz-type methods for solving large nonlinear PDE problems.

随着多核计算机与集群计算的兴起，并行算法成为了求解大规模问题的重要途径，而区域分解法是其中一种被广泛使用的并行算法。已有的区域分解理论分析大多是关于线性偏微分方程，非线性的理论与可用的算法相对较少。然而，在应用上大多数要求解的方程都是非线性的，无论在材料、化学、生物、环境、天气、石油、航天等科目亦然。本项目针对非线性偏微分方程算法的实际需要，在已有非线性算法的基础上，以ASPIN算法及优化传输条件等技巧，设计出一个稳定，可靠，高效，有可扩放性的新并行算法，目的是改善非线性区域分解算法的收敛性与减低算法的总体复杂度。我们将从理论角度分析新算法用于非线性椭圆型问题是的收敛行为，包括非线性迭代的收敛性及每个Newton步中线性迭代法的收敛特性，亦会制定一套基于计算区域几何、网格尺寸、子域数量、方程参数等资料，选择最优传传输条件的方法，为有实际需要并行求解大规模非线性方程者提供参考的依据。

随着多核计算机与集群计算的兴起，并行算法成为了求解大规模问题的重要途径，而区域分解法是其中一种被广泛使用的并行算法。在应用上大多数要求解的方程都是非线性的，无论在材料、化学、生物、环境、天气、石油、航天等科目亦然，可是非线性区域分解法的理论与可用的算法相对较少。本项目针对非线性偏微分方程算法的实际需要，在已有的ASPIN算法的基础上，设计了一套新的RASPEN算法，在求解的子区域问题换上适当的优化传输条件，加速了线性Krylov 的收敛速度，继而结合了各种区域分解方法的独特优点。此外，为保持并行算法的可扩展性，我们设计了一套二水平RASPEN 算法，关键是利用在多重网格算法上已经十分普遍的Full Approximation Scheme来保证不对原来问题的精确解做出修改。我们发现优化RASPEN算法的Jacobian矩阵与线性优化Schwarz 的迭代矩阵非常相似，所以如果根据现行的理论选取最佳的Robin参数，它的非线性收敛也非常快，通常只需要2-3次迭代即可得到准确的逼近解。我们从三个复杂度不一的问题上，发现RASPEN的性能无论是一水平还是二水平都比原本的ASPIN 算法优胜，而且优化RASPEN又比经典的RASPEN算法收敛得更快。