**Previous:** Overlapping Subdomain Methods

**Up:** Domain Decomposition Methods

**Next:** Multiplicative Schwarz Methods

**Previous Page:** Overlapping Subdomain Methods

**Next Page:** Multiplicative Schwarz Methods

The easiest way to describe this approach is through matrix notation. The set of vertices of can be divided into two groups. The set of interior vertices of all and the set of vertices which lies on the boundaries of the coarse triangles in . We shall re-order and as and corresponding to this partition. In this ordering, equation () can be written as follows:

We note that since the subdomains are uncoupled by the boundary vertices,
is block-diagonal
with each block being the stiffness matrix corresponding
to the unknowns belonging to the * interior*
vertices of subdomain .

By a block LU-factorization of , the system in () can be written as:

where is the Schur complement of in .

By eliminating in (), we arrive at the following equation for :

We note the following properties of this Schur Complement system:

- inherits the symmetric positive definiteness of .
- is dense in general and computing it explicitly requires as many solves on each subdomain as there are points on each of its edges.
- The condition number of is , an improvement over the growth for .
- Given a vector defined on the boundary vertices of , the matrix-vector product can be computed according to where involves independent subdomain solves using .
- The right hand side can also be computed using independent subdomain solves.

We shall first describe the Bramble-Pasciak-Schatz preconditioner [35]. For this, we need to further decompose into two non-overlapping index sets:

where denote the set of nodes corresponding to the vertices 's of , and denote the set of nodes on the edges 's of the coarse triangles in , excluding the vertices belonging to .

In addition to the coarse grid interpolation and restriction operators defined before, we shall also need a new set of interpolation and restriction operators for the edges 's. Let be the pointwise restriction operator (an matrix, where is the number of vertices on the edge ) onto the edge defined by its action if but is zero otherwise. The action of its transpose extends by zero a function defined on to one defined on .

Corresponding to this partition of , can be written in the block form:

The block can again be block partitioned, with most of the subblocks being zero. The diagonal blocks of are the principal submatrices of corresponding to . Each represents the coupling of nodes on interface separating two neighbouring subdomains.

In defining the preconditioner, the action of is needed. However, as noted before, in general is a dense matrix which is also expensive to compute, and even if we had it, it would be expensive to compute its action (we would need to compute its inverse or a Cholesky factorization). Fortunately, many efficiently invertible approximations to have been proposed in the literature (see Keyes and Gropp [136]) and we shall use these so-called interface preconditioners for instead. We mention one specific preconditioner: where is an one dimensional Laplacian matrix, namely a tridiagonal matrix with 2's down the main diagonal and -1's down the two off-diagonals, and is taken to be some average of the coefficient of () on the edge . We note that since the eigen-decomposition of is known and computable by the Fast Sine Transform, the action of can be efficiently computed.

With these notations, the Bramble-Pasciak-Schatz preconditioner is defined by its action on a vector defined on as follows:

Analogous to the additive Schwarz preconditioner, the computation of each term consists of the three steps of restriction-inversion-interpolation and is independent of the others and thus can be carried out in parallel.

Bramble, Pasciak and Schatz [35] prove that the condition
number of is bounded by . In
practice, there is a slight growth in the number of iterations as
becomes small (* i.e.*, as the fine grid is refined) or as
becomes large (* i.e.*, as the coarse grid becomes coarser).

The growth is due to the coupling of the unknowns on the
edges incident on a common vertex , which is not accounted for in
. Smith [187] proposed a * vertex space*
modification to which explicitly accounts for this coupling
and therefore eliminates the dependence on and . The idea is
to introduce further subsets of called * vertex spaces*
with consisting of a small set of vertices on
the edges incident on the vertex and adjacent to it. Note that
overlaps with and . Let be the principal
submatrix of corresponding to , and be
the corresponding restriction (pointwise) and extension (by zero)
matrices. As before, is dense and expensive to compute and
factor/solve but efficiently invertable approximations (some using
variants of the operator defined before) have been developed
in the literature (see Chan, Mathew and
Shao [50]). We shall let be such a
preconditioner for . Then Smith's Vertex Space
preconditioner is defined by:

Smith [187] proved that the condition number of is bounded independent of and , provided there is sufficient overlap of with .