Domain Decomposition Methods: Algorithms and Theory

大型代数系统迭代方法的开发是计算流体力学、弹性力学和电磁学高效程序开发的核心。这类代码中的许多其他任务相对容易并行化。因此，代数系统解算器的进展仍然非常重要，因为具有大量快速处理器的并行和分布式计算系统正在变得广泛可用，每个处理器都具有相对大的存储器。域分解算法的一个非常理想的特征是它们尊重现代并行和分布式计算系统的存储层次结构，这对于接近峰值浮点性能是必不可少的。这一点很重要，因为对于大型计算机系统来说，通信成本往往占主导地位。区域分解方法也相对容易实现，并且有越来越坚实的理论基础，这表明收敛速度可以与子域的数量无关，并且只随着分配给单个处理器的子问题的维度而缓慢恶化。这项研究得到了高质量软件系统的支持，特别是由Argonne的PETSc库和合作者支持，他们都是高度成功的并行代码开发人员。为日益复杂的偏微分方程组开发几种区域分解方法的工作将继续下去。区域分解算法是一种迭代方法，通常是预条件共轭梯度类型的迭代方法，用于并行求解当偏微分方程组离散化时产生的大型线性或非线性代数方程组。许多工作都集中在有限元方法上，这使得在该领域发展良好的理论和实践的基础上成为可能。在每个迭代步骤中，精确或近似地解决代表原始问题对潜在大量子区域的限制的局部问题。子区域通常分配给并行计算机的各个处理器，形成问题的整个域的分解。此外，包含粗略组件通常会显著提高预处理器的效率，并可显著减少CPU时间。每一类应用，例如弹性、不可压缩流体流动和电磁学，都需要特别考虑，尤其是为手头的问题设计适当的粗略求解器是至关重要的。在重要的应用中，这个项目现在的主要焦点是电磁学问题。关于几乎不可压缩的弹性和静止的、不可压缩的纳维斯托克斯的工作也将继续。这个项目将把数学分析与算法的设计和数值测试结合起来。分析这些迭代方法的新的强大工具现已成为可能，这使得根据子域的几何性质来预测收敛速度成为可能，即使对于非常不规则的子域，例如使用标准网格剖分产生的子域，这些几何性质也很容易理解。这项工作将通过会议和特邀演讲、教程、期刊文章等提供新的知识传播，对狭隘的研究社区以外的科学计算研究生教育产生影响。此外，由于重点放在广泛使用的方法上，并通过与美国国家实验室和学术界的计算工程科学家直接接触，新的和改进的算法将对这些实验室的重要软件库的发展产生影响。

The development of iterative methods for large algebraic systems is central in the development of efficient codes for computational fluid dynamics, elasticity, and electromagnetics. Many other tasks in such codes parallelize relatively easily. Progress on algebraic system solvers therefore remain very important now that parallel and distributed computing systems, with a substantial number of fast processors, each with a relatively large memory, are becoming widely available. A very desirable feature of domain decomposition algorithms is that they respect the memory hierarchy of modern parallel and distributed computing systems, which is essential for approaching peak floating point performance. This is important since the cost of communication often can dominate for large computer systems. The domain decomposition methods are also relatively easy to implement and they have an increasingly solid theoretical basis, which shows that the rate of convergence can be made independent of the number of subdomains and only deteriorates very slowly with the dimension of the subproblems allocated to individual processors. This research is supported by high quality software systems in particular by Argonne's PETSc library and by collaborators, who are highly accomplished developers of parallel code. Work will continue on developing several families of domain decomposition methods for increasingly complicated systems of partial differential equations. Domain decomposition algorithms are iterative methods, often of preconditioned conjugate gradient type, for the parallel solution of the large linear, or nonlinear, systems of algebraic equations that arise when partial differential equations are discretized. Much of the work is focused on finite element methods which makes it possible to build on the well developed theory and practice of that field. In each iteration step, local problems representing the restriction of the original problem to a potentially large number of subregions are solved exactly or approximately. The subregions, often allocated to individual processors of a parallel computer, form a decomposition of the entire domain of the problem. In addition, the inclusion of a coarse component often substantially increases the efficiency of the preconditioner and can dramatically reduce the CPU time. Each class of applications, e.g., elasticity, incompressible fluid flow, and electromagnetics, requires a special consideration and, in particular, the design of an appropriate coarse solver, for the problem at hand, is crucially important. Of important applications, the main focus of this project is now on problems of electromagnetics. Work on almost incompressible elasticity and stationary, incompressible Navier-Stokes will also continue. This project will combine mathematical analysis with the design and numerical testing of algorithms. New powerful tools for the analysis of these iterative methods are now becoming available, which makes it possible to predict the rate of convergence in terms of geometric properties of the subdomains that are easy to understand even for quite irregular subdomains such as those that result from using standard mesh partitioners. This work will have an impact on graduate education in scientific computing, outside the narrow research community, by providing new knowledge disseminated through conference and invited talks, tutorials, journal articles, etc. Furthermore, with a focus on widely used methods and through direct contact with computational engineering scientists at the US national laboratories and in academia, the new and improved algorithms will have an impact on the development of important software libraries of these laboratories.