Database Reference
In-Depth Information
Algorithm 7.2: (continued)
for
l
d
1
¼
1,
,
n q
(
l
1
1)
...
(
l
d
2
1) do
l
d
¼ n q
(
l
1
1)
...
(
l
d
2
1)
(
l
d
1
1)
e
...
f
l
e
d
1
d
d
,
M
y
i
:¼ e
y
i
þðÞ
x
ð
,
i ¼
1,
...
end for
...
end for
end for
end for
The combination technique is only one of the various methods to solve problems
on sparse grids. Note that there exist also finite difference and Galerkin finite
element approaches which work directly in the hierarchical product basis on the
sparse grid. But the combination technique is conceptually much simpler and easier
to implement. Moreover, it allows to reuse standard solvers for its different sub-
problems and is straightforwardly parallelizable.
7.2.5 Adaptive Sparse Grids
We will now develop an adaptive version of Algorithm 7.1. Note that there are
different types of adaptivity of sparse grids. Here we are interested in data adap-
tivity, i.e., adaptivity with respect to new data points.
We consider the initial data set
S ¼
{(x
i
,
y
i
)}
i¼
1
and apply Algorithm 7.1 to it. As
a result we obtain the solution coefficients
α
l
of (
7.26
) as well as the matrices
C
l
and
B
l
. Suppose now that we get new data points
g
S ¼
f
ð
x
i
;
y
i
Þ
from the same
i
¼
1
distrib
utio
n. We are looking for an
e
fficient procedure to find
α
l
that solves (
7.26
)
for all
M ¼ M þ M
data points of
S ¼ S [ S
, and the solution shall be based on
α
l
and may use
C
l
and
B
l
.
We rewrite the system (
7.26
)as
MC
0
l
þ B
l
B
l
λ
α
l
¼ B
l
y
ð
7
:
29
Þ
with the matrices
C
0
l
and
Bð
j,
i
¼ ϕ
l
,
j
x
ðÞ:
j, k
¼ ∇ϕ
l
,
j
,
∇ϕ
l
,
k
Obviously, now the Laplacian
C
0
l
does not depend on the data points {x
i
}
i¼
1
at
all. Thus, we are looking for the solution of
B
T
l
MC
0
l
þ B
l
λ
α
l
¼ B
l
y
ð
7
:
30
Þ
