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.