Database Reference
In-Depth Information
Solve
Solve
l
= 3
Interpol.
Interpol.
Restrict
Restrict
l
= 2
Interpol.
Interpol.
Restrict
Restrict
l
= 1
Interpol.
Interpol.
Restrict
Restrict
l
= 0
Relax
Relax
Relax
Fig. 6.3 Multigrid method (V cycle) for four levels by two iteration steps
levels is shown schematically in Fig.
6.3
. We are running up the down staircase,
which is also the title of this chapter in acknowledgment of the well-known
American film.
The multigrid method we discussed is summarized in Algorithm 6.1. At this, the
simple iteration method
IT
is called with the current start vector and the right-hand
side as arguments, that is,
x
e
:¼ IT
ð
e
x
,
y
Þ
approximately calculates
K
1
y
,where
e
x
is the start vector, and assigns the result
to
x
.
Notice that the terms “restrictor” and “interpolator” for the inter-level operators
I
f
and
I
g
f
are rather unusual in multilevel approximation theory. In general, we speak
about
restriction
and
interpolation
(or
prolongation
)
.
Most important terms are
restriction operator
,
interpolation operator
(or
prolongator
),
restriction matrix,
and
interpolation matrix
. However, to keep the notation short, we will stick to
restrictor
and
interpolator
.
e
Algorithm 6.1: Multigrid V-cycle
nn
, right-hand side
f
n
, interpolators
I
lþ1
,
Input: coefficient matrix
K
∈
R
∈
R
restrictors
I
lþ1
l
for all levels
l ¼
0,
...
,
l
max
1, number of pre-smoothing steps
n
ν
2
, initial guess
x
0
ν
1
and post-smoothing steps
∈
R
n
von (
6.3
)
Output: approximate solution
x
e
∈
R
1: procedure VCYCLE(
y
l
,
l
)
2:
for
k ¼
1,
...
,
ν
1
do
x
l
:
¼ IT
(
x
l
,
K
l
x
l
y
l
)
3:
⊲
pre-smoothing
4:
end for
y
l
+1
:
¼ I
lþ1
l
(
K
l
x
l
y
l
)
5:
computing the residual
⊲
6:
if
l
+1
<
l
max
then
(continued)