M. Dryja et al., SCHWARZ ANALYSIS OF ITERATIVE SUBSTRUCTURING ALGORITHMS FOR ELLIPTIC PROBLEMS IN 3 DIMENSIONS, SIAM journal on numerical analysis, 31(6), 1994, pp. 1662-1694
Domain decomposition methods provide powerful preconditioners for the
iterative solution of the large systems of algebraic equations that ar
ise in finite element or finite difference approximations of partial d
ifferential equations. The preconditioners are constructed from exact
or approximate solvers for the same partial differential equation rest
ricted to a set of subregions into which the given region has been div
ided. In addition, the preconditioner is often augmented by a coarse,
second-level approximation that provides additional, global exchange o
f information that can enhance the rate of convergence considerably. T
he iterative substructuring methods, based on decompositions of the re
gion into nonoverlapping subregions, form one of the main families of
such algorithms. Many domain decomposition algorithms can conveniently
be described and analyzed as Schwarz methods. These algorithms are fu
lly defined in terms of a set of subspaces and auxiliary bilinear form
s. A general theoretical framework has previously been developed. In t
his paper, these techniques are used in an analysis of iterative subst
ructuring methods for elliptic problems in three dimensions. A special
emphasis is placed on the difficult problem of designing good coarse
models and obtaining robust methods for which the rate of convergence
is insensitive to large variations in the coefficients of the differen
tial equation. Domain decomposition algorithms can conveniently be bui
lt from modules that represent local and global components of the prec
onditioner. In this paper, a number of such possibilities are explored
, and it is demonstrated how a great variety of fast algorithms can be
designed and analyzed.