Domain Decomposition Methods: Algorithms and Theory

点击翻译按钮获取中文摘要

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.