Progress in Engineering Computational Technology
Edited by: B.H.V. Topping and C.A. Mota Soares

Chapter 13

Domain Decomposition Methods on Parallel Computers

J. Kruis
Faculty of Civil Engineering, Czech Technical University, Prague, Czech Republic

Keywords: domain decomposition methods, Schur complement, FETI, DP-FETI, parallel computing.

Creation of parallel computers together with advanced engineering design led to the strong development of domain decomposition methods. Current engineering design deals with very complex structures and problems which result in complicated numerical models with thousands or millions of unknowns (degrees of freedom). Such systems of equations are not solvable in the classical way on single processor computers because they do not have enough memory and they are slow. On the other hand, the parallel computers offer simple solution to the mentioned difficulties. Especially, the flexibility of the PC clusters, which could be enlarged with respect to the required memory, is feasible.

The domain decomposition methods are based on splitting of the original domain into several smaller subdomains. Each subdomain can be processed nearly independently and this fact leads directly to the application of parallel computers. One of the crucial points of the domain decomposition methods is the continuity enforcement, because the solution obtained on particular subdomains must satisfy the continuity conditions. The methods split the unknowns into internal unknowns and boundary unknowns. The boundary unknowns belong to two or more subdomains while the internal unknowns belong to only one subdomain. There are two basic possibilities of the continuity enforcement. The first strategy is based on the special ordering of unknowns (see [4]) while the second possibility deals with the Lagrange multipliers (see [2]).

The so-called coarse, or the reduced, problem is the very important notion in connection with the domain decomposition methods. The internal unknowns are eliminated and only the boundary unknowns are used in the coarse problem. The coarse problem plays an important role in the convergence.

This contribution deals only with the problems which are first discretized and then the discretized form is decomposed into subdomains. The domain decomposition methods can be classified into several groups with respect to various criteria. There are overlapping and non-overlapping domain decomposition methods. In non-overlapping methods, no element is shared by more than one subdomain while in overlapping methods there are several shared elements. The optimal number of shared elements in overlapping methods is not strictly defined. A high number of shared elements leads to faster convergence but it is not efficient with respect to required memory.

The domain decomposition methods can be also classified as the primal and the dual methods. The primal method means that still the original unknowns are used during all computation. The typical example is the Schur complement method applied into mechanical problem solved by the displacement method. The nodal displacements are the unknowns in the original problem as well as in the coarse problem. On the other hand, the FETI method defines the Lagrange multipliers which denote the nodal forces in the mechanical problems solved by the displacement method. The nodal displacements (primal unknowns) are eliminated and the dual unknowns (the Lagrange multipliers) are used in the coarse problem.

The recently introduced dual-primal methods combine features of the primal and dual methods (see [1]). The continuity on the boundaries is enforced by special ordering similarly to the primal methods and by the Lagrange multipliers. The internal unknowns are also eliminated and only unknowns defined on the boundaries create the coarse problem.

Applications of the non-overlapping domain decomposition methods (the Schur complement method, the FETI method and the DP-FETI method) especially in mechanical problems executed on distributed parallel computers are mentioned in [3].

References

1
C. Farhat, M. Lesoinne, K. Pierson, A scalable dual-primal domain decomposition method, Numerical Linear Algebra with Applications, 7, 687-714, 2000.

2
C. Farhat, F.X. Roux, A Method of Finite Element Tearing and Interconnecting and its Parallel Solution Algorithm, International Journal for Numerical Methods in Engineering, 32, 1205-1227, 1991.

3
J. Kruis, Domain Decomposition Methods on Distrubuted Parallel Computers, Saxe-Coburg Publications, UK, in press, 2004.

4
M. Papadrakakis, Solving Large-Scale Problems in Mechanics, The Development and Application of Computational Solution Methods, John Wiley & sons, 1993.

return to the contents page