Previous: Domain Decomposition Methods
Up: Domain Decomposition Methods
Next: Non-overlapping Subdomain Methods
Previous Page: Domain Decomposition Methods
Next Page: Non-overlapping Subdomain 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 () 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 [73] 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 and (essentially it means that the ratio of the distance of the boundary to 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 into 's corresponds to partitioning of the components of the vector into overlapping groups of index sets 's, each with components. The matrix is simply a principal submatrix of corresponding to the index set . is a matrix defined by its action on a vector defined on as: if 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 [173] have experimented with such an algebraic overlapping block Jacobi preconditioner.