Database Reference
In-Depth Information
α
l
¼ B
l
y
B
l
λ
C
l
þ B
l
ð
7
:
26
Þ
with the matrices
and
Cð
j, k
¼ M ∇ϕ
l
,
j
,
∇ϕ
l
,
k
Bð
j,
i
¼ ϕ
l
,
j
x
ðÞ
,
,2
l
t
,
t ¼
1,
j
t
,
k
t
¼
0,
...
...
,
d
,
i ¼
1,
...
,
M
, and the unknown vector
αð
j
,
j
t
¼
,2
l
t
,
t ¼
1,
0,
,
d
. We then solve these problems by a feasible method.
To this end we use here a diagonally preconditioned conjugate gradient algorithm.
But also an appropriate multigrid method with partial semi-coarsening can be
applied. The discrete solutions
f
l
are contained in the spaces
V
l
(see (
7.11
))
of piecewise
d
-linear functions on grid
...
...
Ω
l
.
Note that all these problems are substantially reduced in size in comparison to
(
7.8
). Instead of one problem with the size dim(
V
n
)
¼ O
(
h
n
)
¼ O
(2
nd
), we now
have to deal with
O
(
dn
d
1
) problems of size dim(
V
l
)
¼ O
(
h
n
)
¼ O
(2
n
).
Moreover, all these problems can be solved independently which allows for
a straightforward parallelization on a coarse grain level; see [Gri92]. Also there
is a simple but effective static load balancing strategy available.
Finally, we linearly combine the results
f
l
(x)
¼
∑
j
α
l,j
ϕ
l,j
(x)
∈
V
l
from the
Ω
l
as follows:
different grids
X
ð
n
ðÞ:¼
X
d
1
q¼
0
ðÞ
q
d
1
q
f
f
1
ðÞ:
ð
7
:
27
Þ
jj
1
¼nþ d
1
ð
Þ q
The resulting function
f
ðcÞ
lives in the above-defined sparse grid space
V
ðsÞ
(but
n
n
now with
l
t
>
0in(
7.21
)).
The combination technique can be interpreted as a certain multivariate extrap-
olation method which works on a sparse grid space; for details see [GSZ92]. The
combination solution
f
ðcÞ
n
is in general not equal to the Galerkin solution
f
ðs
n
, but its
accuracy is usually of the same order; see [GSZ92]. To this end, a series expansion
of the error is necessary. Its existence was shown for PDE-model problems in
[BGRZ94].
Note that the summation of the discrete functions from different spaces
V
l
in
(
7.27
) involves
d
-linear interpolation which resembles just the transformation to a
representation in the hierarchical basis (
7.19
). However, we never explicitly assem-
ble the function
f
ðc
n
but rather keep the solutions
f
l
on the different grids
Ω
l
which
arise in the combination formula. Now, any linear operation
F
on
f
ðc
n
can easily be
expressed by means of the combination formula (
7.27
) acting directly on the
functions
f
l
, i.e.,
X
¼
X
d
1
q¼
0
ðÞ
d
1
d
d
Ff
ðÞ
n
FfðÞ:
ð
7
:
28
Þ
jj¼nþ d
1
ð
Þ q
