Domain Decomposition Methods: Algorithms and Theory

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

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.