Database Reference
In-Depth Information
The idea is now to carry this discretization method and its advantages with
respect to the degrees of freedom over to the minimization problem (
7.1
).
The minimization procedure (
7.4
), (
7.5
), and (
7.6
) with the discrete function
f
ðsÞ
in
V
ðsÞ
n
n
ð
n
ðÞ¼
X
jj
1
nþd
1
X
ðÞ
l
,
j
f
I
1
α
ϕ
l, j
ðÞ:
j
∈
would result in the discrete system
T
C
ð
n
þ B
ðÞ
B
ðÞ
n
ðÞ
n
¼ B
ðÞ
n
λ
:
α
y
ð
7
:
24
Þ
n
with
1
;ð
, r
;ðÞ
¼ M ∇ϕ
n
,
and
B
ðÞ
n
1
;ð
,
i
¼ ϕ
n
,
1
;ðÞ
x
ðÞ
,
C
ðÞ
n
ð
,
∇ϕ
n
,
1
;
ðÞ
r
;
j
l
j
1
n
+
d
1, j
∈
I
1
,
j
r
j
1
n
+
d
1. k
∈
I
r
,
i ¼
1,
...
,
M
, and the unknown
ðs
n
)
(r,k)
,
vector (
I
r
. The discrete problem (
7.24
) might in
principle be treated by an appropriate iterative solver. Note that now the size of the
problem is just of the order
O
(
n
d
1
2
n
). Here, the explicit assembly of the matrices
C
ðsÞ
α
j
r
j
1
n
+
d
1, k
∈
n
and
B
ðsÞ
n
should be avoided. These matrices are more densely populated than the
corresponding full grid matrices, and this would add further terms of complexity.
Instead only the action on these matrices on vectors, i.e., a matrix-vector multiplication,
should be performed in an iterative method like the conjugate gradient method or a
multigrid method. For example, for
C
ðs
n
this is possible in a number of operations which
is proportional to the unknown only; see [Bun92]. However, the implementation of such
a program is quite cumbersome and difficult. It also should be possible to avoid the
assembly of
B
ðs
n
and
B
ðs
n
(
B
ðs
n
)
T
and to program the respective matrix-vector multi-
plications in
O
(
n
d
1
2
n
,
M
) operations. But this is complicated as well. Furthermore, the
on-the-fly calculation of the action of these matrices scales with
M
whichshouldbe
avoided for large
M
.
There also exists another variant of a solver working on the sparse grid, the
so-called combination technique [GSZ92], which makes use of multivariate extrap-
olation. In the following, we apply this method to the minimization problem (
7.1
).
It is much simpler to use than the Galerkin approach (
7.24
), it avoids the matrix
assembly problem mentioned above, and it can be parallelized in a natural and
straightforward way.
