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

项目名称： 基于优化Schwarz算法的非线性预条件问题

项目编号： No.11501483

项目类型： 青年科学基金项目

立项/批准年度： 2016

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

项目作者： 郭颖康

作者单位： 香港浸会大学深圳研究院

项目金额： 18万元

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

中文关键词： 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.

英文关键词： Schwarz methods;Domain decomposition;Optimal methods;Convergence