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.