**Previous:** Reduced System Preconditioning

**Up:** Remaining topics

**Next:** Multigrid Methods

**Previous Page:** Reduced System Preconditioning

**Next Page:** Overlapping Subdomain Methods

In recent years, much attention has been given to domain decomposition methods for linear elliptic problems that are based on a partitioning of the domain of the physical problem. Since the subdomains can be handled independently, such methods are very attractive for coarse-grain parallel computers. On the other hand, it should be stressed that they can be very effective even on sequential computers.

In this brief survey, we shall restrict ourselves to the standard second order self-adjoint scalar elliptic problems in two dimensions of the form:

where is a positive function on the domain , on whose boundary the value of is prescribed (the Dirichlet problem). For more general problems, and a good set of references, the reader is referred to the series of proceedings [172][135][106][48][47][46].

For the discretization of (), we shall assume for
simplicity that is triangulated by a set of nonoverlapping
coarse triangles (subdomains) with internal
vertices. The 's are in turn
further refined into a set of smaller triangles
with *n* internal vertices in total.
Here denote the coarse and fine mesh size respectively.
By a standard Ritz-Galerkin method using piecewise linear triangular
basis elements on (), we obtain an
symmetric positive definite linear system
.

Generally, there are two kinds of approaches depending on whether the subdomains overlap with one another (Schwarz methods) or are separated from one another by interfaces (Schur Complement methods, iterative substructuring).

We shall present domain decomposition methods as preconditioners
for the linear system
* or* to
a reduced (Schur Complement) system
defined on the interfaces in the non-overlapping formulation.
When used with the standard Krylov subspace methods discussed
elsewhere in this book, the user has to supply a procedure
for computing or given or and the algorithms to be described
herein computes .
The computation of is a simple sparse matrix-vector
multiply, but may require subdomain solves, as will be described later.