General
Domain Decomposition Methods (DDM) divide the original physical model into smaller subdomains, which are processed independently and periodically coordinate to solve the original problem. This section lists some common characteristics of most DDMs.
Freedom degrees (dofs) of each subdomain are divided into boundary, which correspond to nodes on the boundary between two or more subdomains, and internal, which correspond to nodes belonging only to one subdomain. E.g. in an elasticity problem, if us are the displacements corresponding to the dofs of subdomain s, b denotes boundary dofs and i denotes internal dofs:
Many computationally intensive operations can then be performed for each subdomain independently. E.g. in an elasticity problem, the stiffness matrices K and force vectors (right hand side vectors) f can be calculated for each subdomain and then divided into their “internal” and “boundary” parts:
Apart from the examples above, many other operations may be used by specific solvers, such as factorizing the stiffness matrix or its submatrices, calculating Schur complements, etc. However they can usually be performed for each subdomain independently. There is also the need to transfer various quantities between subdomain and global vectors and matrices, especially those corresponding to boundary dofs. This is achieved by using special boolean matrices, whose entries are 0 or 1. E.g to map boundary displacements from global to subdomain level, we use the boolean matrix Lb:
In addition, global forces and stiffnesses can be obtained by adding the contribution of each subdomain after applying the inverse map:
where Ns is the number of subdomains. After determining the quantities above, a typical DDM solver constructs and solves an interface problem. Interface problem are linear systems that involve only boundary dofs and are thus much smaller than the original one. They are usually solved by using an iterative method, e.g. PCG if the interface problem matrix is symmetric positive definite. Iterative methods require matrix-vector multiplications, which in DDM are performed in a distributed fashion. E.g instead of calculating the global Kbb as above, which requires a lot of coordination and extra memory, and then multiplying vectors,
one would typically multiply the vector with each subdomain Kbb and then add the results:
Since iterative methods are used, a preconditioner is always necessary. Each DDM defines its own preconditioners. DDM preconditioners are also stored and used in a distributed fashion, like the matrix-vector multiplication shown above: each subdomain stores its own contribution to the preconditioner matrix and during the preconditioning step, each preconditioner submatrix is applied independently and the results are added.
The most efficient DDMs also comprise a coarse problem, which is different for each method. The coarse problem of a DDM is a linear system contained in the interface problem and its purpose is to speed up the distribution of the global error among subdomains. The coarse problem is much smaller than the interface problem and it is solved during each iteration of the iterative method used for the interface problem. In general, the coarse problem tries to represent the behaviour of each subdomain using a very limited number of dofs or other features.
Advantages and drawbacks
DDM solvers are among the most efficient ones for computationally intensive problems. Most operations are performed independently for each subdomain, therefore they can be run in parallel and coordination is needed only for global level operations, which are typically fewer and lightweight. Since each subdomain defines its own matrices, distributed memory systems (e.g. many networked computers) can be used to satisfy the memory requirements of even the largest problems. Thus, DDM solvers can leverage all the power of modern computational systems to substantially reduce the time needed for large scale simulations.
Compared to iterative solvers, the iterations required by the most efficient DDMs require significantly less iterations and are less sensitive to the linear system matrix size and condition. The preconditioner is also usually defined by the DDM, instead of being left to the user’s choice. Moreover DDMs that perform matrix factorization, do so at subdomain level or during the coarse problem preparation. Compared to direct solvers, the size and bandwidth of these matrices is significantly smaller, which alleviates most of the problems direct solvers face for 3D and some 2D problems.
On the other hand, applying a DDM is not as straightforward, since the original physical model must also be decomposed into subdomains. In addition every analysis operation, including the solution of linear systems, must take into account this decomposition. Furthermore coordinating between subdomains and setting up the auxiliary matrices, vectors and other quantities of a DDM solver incurs a computational overhead. For problems with only a few dofs this overhead is not negligible. In conclusion DDM solvers are a very attractive or the only possible option for large scale simulations, especially 3D and some intensive 2D problems.