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  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
is simply a principal submatrix of
corresponding to the index set
matrix defined by its action on a vector
but is zero otherwise. Similarly, the action of its transpose
-vector by picking off the components of
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  have experimented with such an algebraic overlapping block Jacobi preconditioner.