Engineering Computational Technology
Chapter 9 P.K. Jimack
School of Computing, University of Leeds, United Kingdom Keywords: partial differential equations, domain decomposition, parallel computing.
Domain decomposition methods have been applied to the solution of engineering problems for many years. Over the past two decades however the growth in the use of parallel computing platforms has ensured that interest in these methods, which offer the possibility of parallelism in a very natural manner, has become greater than ever. This interest has led to research that has yielded significant advances in both the theoretical understanding of the underlying mathematical structure behind domain decomposition methods and in the variety of domain decomposition algorithms that are available for use by the engineering community. In this paper we provide a brief overview of some of the main categories of domain decomposition algorithm and then focus on a particular variant of the overlapping Schwarz algorithm that is based upon the use of a hierarchy of finite element (FE) grids. Throughout the paper we consider domain decomposition methods as preconditioners for standard, Krylov subspace, iterative solvers however they may also be used directly as iterative methods in their own right. All of the theoretical results that are described apply equally in both cases. The aim of the paper is also to introduce the reader to some of the main aspects of domain decomposition preconditioning. This includes a motivation for DD methods through their applicability to the solution of PDEs using parallel computing architectures. Given that this is the main motivation for using these methods the paper also provides a short overview of the parallel assembly of finite element systems of equations based upon a geometric decomposition of the problem. This decomposition requires that the FE grid be partitioned and that this partition be mapped onto the processor network in some way. The bulk of the content is concerned with overlapping Schwarz preconditioners, their theoretical properties and their practical parallel implementation. From a theoretical point of view two fundamental theorems are presented concerning the quality of additive Schwarz methods. The first of these states that, provided the finite element subspaces that are associated with each subdomain form a stable splitting (as defined within the paper) of the global finite element space, then the condition number of the preconditioned system is bounded. The second result then shows that if there is a sufficiently large overlap between the subdomains and a coarse grid problem is also solved then the subdomain spaces do indeed form a stable splitting of the global space and the resulting preconditioner is optimal. Unfortunately the computational cost associated with maintaining a large overlap between the subdomains is not justified in terms of practical performance, and so the use of alternative domain decomposition strategies is discussed. This leads to the proposal of a new strategy (see [2] for full details) which combines many of the features of the optimal two level algorithm with those of optimal multilevel methods. This approach makes use of a nested hierarchy of finite element grids in such a way that each subdomain problem has an overlap layer of precisely one element at each level of the refinement. A brief theoretical justification of this ``weakly overlapping'' preconditioner is described and then its practical parallel implementation is discussed. The results of a number of computational experiments are also included. Following this two extensions of the technique are proposed. The first of these (see [1]) is to introduce a restricted version of the preconditioner, which is non-symmetric even for a symmetric problem, and the second is to apply the restricted preconditioner to convection-dominated convection-diffusion problems (see [3,4,5]). Again numerical results are included to demonstrate both the quality of the preconditioner and the efficiency of the parallel implementation.
References
| ||||||||||
