Scalable Parallel Multilevel Domain Decomposition Methods

可扩展的并行多级域分解方法

• 批准号: 0612574
• 负责人: Jing Li
• 金额: $ 8.42万
• 依托单位: Kent State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-08-15 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0612574&HistoricalAwards=false
• 关键词: Scalable; Parallel; Multilevel; Domain; Decomposition

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.

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