Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

Computational Science, Engineering & Technology Series
ISSN 17593158 CSETS: 8
ENGINEERING COMPUTATIONAL TECHNOLOGY Edited by: B.H.V. Topping, Z. Bittnar
Chapter 9
Domain Decomposition Preconditioning for Parallel PDE Software P.K. Jimack
School of Computing, University of Leeds, United Kingdom P.K. Jimack, "Domain Decomposition Preconditioning for Parallel PDE Software", in B.H.V. Topping, Z. Bittnar, (Editors), "Engineering Computational Technology", SaxeCoburg Publications, Stirlingshire, UK, Chapter 9, pp 193219, 2002. doi:10.4203/csets.8.9
Keywords: partial differential equations, domain decomposition, parallel computing.
Summary
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 nonsymmetric even for a symmetric problem, and the second is to apply the restricted preconditioner to convectiondominated convectiondiffusion 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
purchase the fulltext of this chapter (price £20)
go to the previous chapter 
