Database Reference
In-Depth Information
Algorithm 6.1: (continued)
x
l
+1
:
¼
VCYCLE(
y
l
+1
,
l
)
7:
recursive calls at coarser grid
⊲
8:
else
x
l
+1
:
¼
(
K
l
+1
)
1
y
l
+1
9:
direct solver on the coarsest grid
⊲
10:
end if
x
l
:
¼ x
l
+
I
lþ1
x
l
+1
11:
coarse grid correction
⊲
12:
for
k ¼
1,
...
,
ν
2
do
x
l
:
¼ IT
(
x
l
,
K
l
x
l
y
l
)
13:
⊲
post-smoothing
14: end for
15: return
x
l
16: end procedure
17: return VCYCLE(
f
,0)
initial call
⊲
We do not wish here to explore the complicated refinements and numerous
variants of the multigrid approach, much less the mathematical proof of its opti-
mality. What is critical is the fundamental idea:
Multigrid approach: If for an operator equation the high-frequency error
components can be quickly reduced by classic iteration methods, the use of
the multigrid methods in the concrete and multi-scale methods in general leads
to the efficient solution of the operator equation. This applies particularly to
wide classes of differential and integral equations.
Now the multigrid approach is not a basis transformation (since the multigrid
hierarchy, which represents a
generating system
, is not unique in relation to the
coefficient splitting and thus is not a basis), but it is possible to find multi-scale
bases which work equally well. For this, what we call
wavelets
play a central role.
Wavelets have a long history; modern wavelet theory is largely based on St
´
phane
Mallat
multiresolution analysis
[Ma99] and the work of Ingrid Daubechies
[Dau92].
Wavelets are a combination of nodal and global multi-scale bases: they use
multiple levels, but always a quasi-local support. The
multilevel basis
in Fig.
6.2b
is
essentially a wavelet basis (more precisely, a bi-orthogonal wavelet basis), although
classic wavelets are orthogonalized and hence more complicated.
Although the uncertainty principle (
6.2
) still applies for wavelets of course, in
many respects they constitute an optimal compromise between a nodal and global
multi-scale basis: they are asymptotically optimal for the smoothing and compres-
sion of smooth signals and for solving differential and integral equations. In
addition, using special anisotropic grids which we call
sparse grids,
it is possible
for the first time to approximate high-dimensional smooth functions efficiently. By
this means, for instance, differential equations in a 20-dimensional space can be
solved (Fig.
6.4
).
