Overlapping Subdomain Methods

next up previous contents index
Next: Non-overlapping Subdomain Methods Up: Domain Decomposition Methods Previous: Domain Decomposition Methods

Overlapping Subdomain Methods


In this approach, each substructure is extended to a larger substructure containing internal vertices and all the triangles , within a distance from , where refers to the amount of overlap.

Let denote the the discretizations of (gif) on the subdomain triangulation and the coarse triangulation respectively.

Let denote the extension operator which extends (by zero) a function on to and the corresponding pointwise restriction operator. Similarly, let denote the interpolation operator which maps a function on the coarse grid onto the fine grid by piecewise linear interpolation and the corresponding weighted restriction operator.

With these notations, the Additive Schwarz Preconditioner for the system can be compactly described as:

Note that the right hand side can be computed using

subdomain solves using the

's, plus a coarse grid solve using

, all of which can be computed in parallel. Each term

should be evaluated in three steps: (1) Restriction:

, (2) Subdomain solves for


, (3) Interpolation:

. The coarse grid solve is handled in the same manner.

The theory of Dryja and Widlund [76] shows that the condition number of

is bounded independently of both the coarse grid size

and the fine grid size

, provided there is ``sufficient'' overlap between


(essentially it means that the ratio

of the distance

of the boundary


should be uniformly bounded from below as

.) If the coarse grid solve term is left out, then the condition number grows as

, reflecting the lack of global coupling provided by the coarse grid.

For the purpose of implementations, it is often useful to interpret the definition of

in matrix notation. Thus the decomposition of


's corresponds to partitioning of the components of the vector


overlapping groups of index sets

's, each with

components. The


is simply a principal submatrix of

corresponding to the index set


is a

matrix defined by its action on a vector

defined on



but is zero otherwise. Similarly, the action of its transpose

forms an

-vector by picking off the components of

corresponding to

. Analogously,

is an

matrix with entries corresponding to piecewise linear interpolation and its transpose can be interpreted as a weighted restriction matrix. If

is obtained from

by nested refinement, the action of

can be efficiently computed as in a standard multigrid algorithm. Note that the matrices

are defined by their actions and need not be stored explicitly.

We also note that in this algebraic formulation, the preconditioner

can be extended to any matrix

, not necessarily one arising from a discretization of an elliptic problem. Once we have the partitioning index sets

's, the matrices

are defined. Furthermore, if

is positive definite, then

is guaranteed to be nonsingular. The difficulty is in defining the ``coarse grid'' matrices

, which inherently depends on knowledge of the grid structure. This part of the preconditioner can be left out, at the expense of a deteriorating convergence rate as

increases. Radicati and Robert [178] have experimented with such an algebraic overlapping block Jacobi preconditioner.  

next up previous contents index
Next: Non-overlapping Subdomain Methods Up: Domain Decomposition Methods Previous: Domain Decomposition Methods

Jack Dongarra
Mon Nov 20 08:52:54 EST 1995