Database Reference
In-Depth Information
introduced above. It was initiated in 1982 by Achi Brandt, Steve McCormick, and
John Ruge [BMR82] and especially improved by St¨ben [TOS01].
The historical starting point was the recognition that FEM equations in technical
practice are often solved for objects with complex structures (house roofs, cars,
airplanes, etc.). Thus, it is difficult to define a hierarchy on the FEM grids. Now
however it has been established, in particular for discretized differential equations
(
6.3
) under consideration of their eigenvalue properties of the stiffness matrix
K
,
that
algebraic smooth error vectors
arise. That means that while local errors are
quickly reduced by iteration methods, the smooth error components reduce only
relatively slowly. However, according to our multigrid approach, multilevel
methods are outstandingly suitable for solution of these problems.
In contrast to the analytical multigrid, the proofs of the convergence speed are
often incomplete in the algebraic case. In practice however AMG has proven itself
very powerful in most cases.
In what follows, we shall provide a brief, but mathematically sound introduction
to algebraic multigrid methods. To this end, we need to stipulate an algebraic notion
of a grid and specify what is meant by an algebraically smooth error vector.
Consider a system of linear equations of the form
Ax ¼ b
,
ð
6
:
4
Þ
where
A
is a non-singular real
NN
-matrix and
b
is a real vector of length
n
, and let
(
M, N
)bea
splitting
of
A
, that is,
A ¼ M-N
and
M
is non-singular. It can easily be
verified that the sequence of iterates generated by the update rule
:¼ x þ M
1
b Ax
x
ð
Þ:
ð
6
:
5
Þ
converges to the solution of (
6.4
) for all initial guesses if and only if the
spectral
radius
, that is, the largest modulus of the eigenvalues, of the iteration matrix
S
:
¼ M
1
N
is strictly smaller than 1. Moreover, the spectral radius of
S
coincides
with the asymptotic rate of convergence (with respect to
any
norm).
Hence, if the spectral radius of
S
is close to 1, the method will exhibit slow
convergence. In the above introduced setting where (
6.4
) is a finite differences
discretization of a Poissonian boundary value problem, it holds that the spectral
radius of the discretized system converges to 1 as the number of grid points
increases. Hence, both the cost of one iteration and the number of iterations required
to achieve a prescribed accuracy growwith the number of grid points. Expressing the
error in terms of a basis of eigenvectors of the iteration matrix, one observes that
the coefficients converge to 0 at an asymptotic rate given by the magnitude of
the corresponding eigenvalue. In the PDE setting, this is the algebraic explanation
for slow convergence of smooth errors. In the case where
A
is a discretization of a
Laplacian differential operator, eigenvectors of the iteration matrix corresponding to
eigenvalues close to 1 are geometrically
smooth
, whereas those corresponding to
small eigenvalues are
oscillatory.
In a purely algebraic setting where there is no
underlying differential equation, we retain this geometric intuition as a metaphor
