Information Technology Reference
In-Depth Information
the sparse tensor product matrices is once again bounded independently of the mesh
width. We see, therefore, that the increased computational complexity of the pricing
of multi-asset options or options in SV market models can be practically removed
by the sparse tensor product construction.
Dimensionality reduction by principal component analysis is investigated in or-
der to price options on indices by considering the whole vector process of all of their
constituents.
13.1 Sparse Tensor Product Finite Element Spaces
Consider the space
V
L
=
span
{
ψ
,k
:
0
≤
≤
L, k
∈∇
}
as in Chap. 12, where the
wavelets
ψ
,k
:
(
0
,
1
)
→ R
are assumed to be generated from a single-scale basis
Φ
L
of approximation order
p
.Now,let
G
(
0
,
1
)
d
,
d>
1 and define the full tensor
:=
product space
V
L
as the
d
-fold tensor product of
V
L
,i.e.
V
L
:=
V
L
.
(13.1)
1
≤
i
≤
d
As an example, consider the continuous, piecewise linear wavelets of Exam-
ple 12.1.1. Then,
V
L
is the same space as in (8.19). Writing
ψ
,
k
(x)
:=
ψ
1
,k
1
(x
1
)
···
ψ
d
,k
d
(x
d
)
for an arbitrary tensor product wavelet,
V
L
can be written as
V
L
=
span
{
ψ
,
k
:
0
≤
i
≤
L, k
i
∈∇
i
,i
=
1
,...,d
}
.
Using the decomposition of
V
L
=
V
L
−
1
⊕
W
L
,
V
0
=
W
0
into its increment spaces,
we also can write
V
L
in terms of increment spaces
W
1
⊗···⊗
W
d
.
V
L
=
0
≤
i
≤
L
Since dim
W
i
(
2
Ld
)
degrees of freedom which grow
exponentially with increasing dimension
d
. To avoid this “curse of dimension”, we
introduce the sparse tensor product space
V
L
:=
(
2
i
)
, the space
=
O
V
L
has
O
span
{
ψ
,
k
:
0
≤
1
+···+
d
≤
L, k
i
∈∇
i
,i
=
1
,...,d
}
W
1
⊗···⊗
=
W
d
.
(13.2)
0
≤
1
+···+
d
≤
L
The difference between the tensor product space
V
L
and the sparse tensor product
space
V
L
isshowninFig.
13.1
for level
L
=
3 and
d
=
2 using wavelets as described
in Example 12.1.1.
Lemma 13.1.1
The dimension N
L
:=
dim
V
L
of
V
L
is N
L
=
O
(
2
L
L
d
−
1
)
.
d
Proof
Let
I
L
:= {
∈ N
0
||
|
1
∈
(L
−
1
,L
]}
and
dim
C
C
2
L
W
1
W
d
2
|
|
1
K
L
:=
⊗···⊗
≤
=
1
∈
I
L
∈
I
L
∈
I
L
Search WWH ::
Custom Search