Domain Decomposition Methods: Algorithms and Theory

大型代数系统数值方法的发展是计算流体动力学、弹性学和电磁学有效代码发展的核心。这种代码中的许多其他任务相对容易并行化。因此，随着并行和分布式计算系统的数量不断增加，代数系统解算器仍然非常重要，这些系统具有大量快速处理器，每个处理器都具有相对较大的内存，正变得广泛可用。域分解算法的一个非常理想的特征是，它们尊重现代并行和分布式计算系统的内存层次结构，这对于接近峰值浮点性能是必不可少的。这一点很重要，因为对于大型计算机系统来说，通信成本往往占主导地位。领域分解方法也相对容易实现，并且具有越来越坚实的理论基础，这表明这些预处理Krylov空间方法的收敛速度与子领域的数量无关，并且随着分配给单个处理器的子问题的维数的增加而缓慢增长。在每个迭代步骤中，精确或近似地解决局部问题，这些局部问题表示原始问题对潜在大量子区域的限制。子区域可以分配给并行计算机的各个处理器，形成问题的整个域的分解。此外，包含粗组件通常会大大提高预处理器的效率，并可以显著减少CPU时间。这个项目将数学分析与算法的设计和数值测试相结合。每一类应用，如弹性、不可压缩流体流动和电磁学，都需要特别考虑，特别是，为手头的问题设计合适的粗解器是至关重要的。要考虑的应用包括不可压缩的Navier Stokes方程、Reissner-Mindlin板、Maxwell方程、非线性弹性接触问题以及在强迫振动和声学中产生的问题。工作还将继续开发分析工具，这些工具也适用于非常不规则的子域，例如从网格划分软件中获得的子域。这项工作的总体目标是为工程和科学界提供改进的计算方法。特别强调的是可以有效地用于现代并行和分布式计算机系统的方法；这些系统有许多处理器和用于处理器之间通信的快速网络。在许多设计问题中，为了考虑复杂的几何形状和快速变化的位移或速度，需要如此大规模的计算资源，而标准的计算系统往往被证明是不够的。在美国国家实验室和计算机制造商的领导下，大规模并行计算系统正在迅速发展，这些系统现在也可供实践工程师使用，例如，在认证和施工之前，在地震影响下测试建筑设计，或者在实际操作条件下测试机器零件，在制作原型之前。这项工作需要访问软件系统，最终需要可靠的方法来近似复杂的科学或工程模型。在许多应用中，准确的预测通常需要大量的数据来足够准确地描述几何形状和材料属性。设计提取这些问题的解的方法需要针对不同的应用（如建筑物的设计、电磁波的传播或油田中的流体流动）使用不同的算法。本项目着重于这些问题的数学分析和改进方法的设计。过去此类工作的经验清楚地表明，从此类工作中获得的见解可以大大提高计算实践的效率和可靠性。这项工作是与位于新墨西哥州阿尔伯克基的SANDIA国家实验室和德国埃森大学的主要方法和软件系统开发人员合作完成的。

The development of numerical methods for large algebraic systems iscentral in the development of efficient codes for computationalfluid dynamics, elasticity, and electromagnetics. Many other tasks in such codes parallelize relatively easily.Algebraic system solvers therefore remain very important now thatan increasing number of parallel and distributed computing systems, witha substantial number of fast processors, each with a relatively large memory,are becoming widely available. A very desirable feature of domaindecomposition algorithms is that they respect the memory hierarchy ofmodern parallel and distributed computing systems, which is essentialfor approaching peak floating point performance. This is importantsince the cost of communication often can dominate for large computersystems. The domain decomposition methods are also relatively easy to implement and they have an increasingly solid theoretical basis, which shows that therates of convergence of these preconditioned Krylov space methods are independent of the number of subdomains and grows only very slowly with the dimension of the subproblems allocated to individual processors. 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, which can be 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 preconditionerand can dramatically reduce the CPU time. This project will combine mathematical analysis with the design and numerical testing of algorithms.Each class of applications, e.g., elasticity, incompressible fluid flow,and electromagnetics, requires special considerations and,in particular, the design of an appropriate coarse solver, for the problem at hand, is crucially important. Among the applications to be considered are incompressible Navier Stokes equations, Reissner-Mindlin plates, Maxwell's equations, nonlinear elastic contact problems, and those arising in forced vibrations and acoustics. Work will also continue on developing analytic tools, which also are applicable to very irregular subdomains such as those obtained from mesh partitioning software.The overall goal of this work is to provide improved computational methodsfor the engineering and scientific community. A special emphasis is onmethods that can be used effectively on modern parallel and distributedcomputer systems; these systems have many processors and fast networksfor the communication between the processors. In many design problems, suchlarge scale computing resources are required in order to take complicatedgeometry and rapidly varying displacements or velocities into account andstandard computing systems have often proved to be inadequate. Led by theUS national laboratories and the computer manufacturers, large scale parallelcomputing systems are being developed rapidly and these systems are by nowalso available to practicing engineers, who, e.g., test building designunder the impact of earthquakes, prior to certification and construction, or machine parts under realistic operating conditions, prior to making prototypes. This work requires access to software systems and ultimately to reliable methods to approximate complicated scientific or engineering models. In many applications, accurate predictions often require massive amounts of data to describe the geometry and material properties accuratelyenough. The design of methods to extract the solution of such problems requires different algorithms for different applications such as thedesign of buildings, the propagation of electromagnetic waves, or fluid flow in oil fields. This project is focused on mathematical analysisof these issues and the design of improved methods. Experience of such efforts in the past clearly indicates that insight gained from such work can greatly improve the efficiency and reliability of computational practice. This work is a collaborative effort with leading developers of methods and software systems at the SANDIA National Laboratories at Albuquerque, NM, and at the University of Essen, Germany.