Scalable Parallel Multilevel Domain Decomposition Methods

在许多科学和工程问题中，求解大型线性方程组往往是计算成本最高的部分。求解大型线性方程组的可扩展并行算法的设计是科学计算中最重要的问题之一。其中最有效的并行迭代方法是并行多重网格方法、多层矩阵预条件和区域分解方法。区域分解方法是并行实现的理想方法。但目前的多层区域分解算法都没有表现出令人信服的并行可伸缩实验结果，而且在实际应用中，收敛速度往往随着层数的增加而恶化。另一方面，对求解某些对称正定问题的多重网格V-圈，从理论和实验上证明了其一致收敛速度。但多栅格V循环的并行性能远远不能令人满意。该项目的主要目标是设计和分析可伸缩的并行多层区域分解方法，并研究相关并行多层迭代方法之间的联系。对于这些内在联系的多层预条件，坚实的理论基础应该是有效的。这一理论将为可伸缩并行多层迭代方法的设计提供实践指导。本项目将研究所提出的算法在重要的科学和工程计算问题中的应用，例如弹性问题、Stokes/Navier-Stokes问题、弹性结构振动问题和声散射问题。这些问题与飞机设计、声纳、雷达、物探、医学成像、无损检测等诸多技术息息相关。

Solving large linear systems of equations is often the most computationally expensive part in many scientific and engineering problems. The design of scalable parallel algorithms for solving large linear systems of equations is one of the most important problems in scientific computing. Among the most effective parallel iterative methods are parallel multigrid methods, multilevel matrix preconditioners, and domain decomposition methods. Domain decomposition methods are ideal for parallel implementation. But none of the current multilevel domain decomposition algorithms has shown convincing parallel scalable experimental results, and in practice the convergence rates often deteriorate with the increase of the number of levels. On the other hand, a uniform convergence rate has been proved, both theoretically and experimentally, for the multigrid V-cycles for solving certain symmetric positive definite problems. But the parallel performance of multigrid V-cycles is much less satisfactory. The main goals in this project are the design and analysis of scalable parallel multilevel domain decomposition methods, and the study of connections between the related parallel multilevel iterative methods. A solid theoretical foundation should be valid for these inherently related multilevel preconditioners. Such a theory will provide a practical guide for the design of scalable parallel multilevel iterative methods.Applications of the proposed algorithms to important scientific and engineering computational problems, e.g., elasticity problems, Stokes/Navier-Stokes problems, elastic structure vibration problems, and acoustic scattering problems, will be studied in this project. These problems are closely connected with many technologies such as aircraft design, sonar, radar, geophysical exploration, medical imaging and nondestructive testing.