216
9 High-Dimension Model Representation via Sparse GridTechniques
whether we can reduce the number of runs by reducing the number of nodes in
the interpolating grid. The answer lies in the notion of ‘sparse grids.’ This is an
important area of study in numerical methods, and we refer the reader to [43] for a
brief tutorial. We will follow the presentation and nomenclature of [43], using the
complex-flaw model of Fig. 6.3 as an example. Further interesting applications of
the sparse grid approach can be found in [44] and [146].
Referring to Fig. 6.3, we can define the mathematical structure of the problem
by the abstract formula (0, 10, 20) ⊗ (0, 10, 20) ⊗ (0, 10, 20) ⊗ (0, 10, 20),
where ⊗ represents the Cartesian or ‘direct’ or ‘tensor’ product. Thus, we have
a problem that is defined on a four-dimensional hypercube with 16 corner nodes,
given by (0, 20) ⊗ (0, 20) ⊗ (0, 20) ⊗ (0, 20) and 65 interior nodes given by the
‘direct-difference’ between the total nodes given above and the corner nodes. These
involve the intermediate 10mil levels in Fig. 6.3. The question then becomes, are
all of the interior nodes required for an accurate representation of the function, and
if not, how do we choose which ones to keep? The answer to this is given by the
sparse grid algorithm.
The sparse grid algorithm of [43] relies on a refinement of the interval of interest
through successive halving of the previous interval, and then using the ‘hierarchical’
basis system of Fig. 9.1 as the interpolants. This system comprises, of course, our
famous one-dimensional, first-order spline tent functions:
φ l,j =
1 − |x/ h l − j l |, x ∈ [(j l − 1)h l , (j l + 1)h l ] ∩ |0, 1|;
0,
otherwise,
,
(9.1)
where h l is the length of an interval in the lth level, and j l = 0, . . . , 2 l determines
the position of a node. It is assumed in [43] that the grid is defined on the unit cube,
which is the reason for the appearance of the interval, [0, 1]. For our problem, we
are only interested in levels 0 and 1 of the hierarchy, because we only use at most
two intervals for each dimension (variable) of the problem, as shown in Fig. 6.3.
Multidimensional functions are obtained by taking products of the onedimensional splines:
φ l,j = Π
d
t=1 φ l t ,j t (x t ) ,
(9.2)
where l = (l 1 , . . . , l d ) denotes the number of intervals at the lth level in each
dimension. Each entry is an integer. Similarly, j = (j 1 , . . . , j d ), with j t =
0, . . . , 2 l t , denotes the nodal ordering at the lth level in each dimension. Associated
with the multidimensional functions is the index set
B l =
j t = 1, . . . , 2 l t − 1, j t odd, t = 1, . . . , d, if l t > 0,
j t = 0, 1,
t = 1, . . . , d, if l t = 0 .
(9.3)
9 High-Dimension Model Representation via Sparse GridTechniques
whether we can reduce the number of runs by reducing the number of nodes in
the interpolating grid. The answer lies in the notion of ‘sparse grids.’ This is an
important area of study in numerical methods, and we refer the reader to [43] for a
brief tutorial. We will follow the presentation and nomenclature of [43], using the
complex-flaw model of Fig. 6.3 as an example. Further interesting applications of
the sparse grid approach can be found in [44] and [146].
Referring to Fig. 6.3, we can define the mathematical structure of the problem
by the abstract formula (0, 10, 20) ⊗ (0, 10, 20) ⊗ (0, 10, 20) ⊗ (0, 10, 20),
where ⊗ represents the Cartesian or ‘direct’ or ‘tensor’ product. Thus, we have
a problem that is defined on a four-dimensional hypercube with 16 corner nodes,
given by (0, 20) ⊗ (0, 20) ⊗ (0, 20) ⊗ (0, 20) and 65 interior nodes given by the
‘direct-difference’ between the total nodes given above and the corner nodes. These
involve the intermediate 10mil levels in Fig. 6.3. The question then becomes, are
all of the interior nodes required for an accurate representation of the function, and
if not, how do we choose which ones to keep? The answer to this is given by the
sparse grid algorithm.
The sparse grid algorithm of [43] relies on a refinement of the interval of interest
through successive halving of the previous interval, and then using the ‘hierarchical’
basis system of Fig. 9.1 as the interpolants. This system comprises, of course, our
famous one-dimensional, first-order spline tent functions:
φ l,j =
1 − |x/ h l − j l |, x ∈ [(j l − 1)h l , (j l + 1)h l ] ∩ |0, 1|;
0,
otherwise,
,
(9.1)
where h l is the length of an interval in the lth level, and j l = 0, . . . , 2 l determines
the position of a node. It is assumed in [43] that the grid is defined on the unit cube,
which is the reason for the appearance of the interval, [0, 1]. For our problem, we
are only interested in levels 0 and 1 of the hierarchy, because we only use at most
two intervals for each dimension (variable) of the problem, as shown in Fig. 6.3.
Multidimensional functions are obtained by taking products of the onedimensional splines:
φ l,j = Π
d
t=1 φ l t ,j t (x t ) ,
(9.2)
where l = (l 1 , . . . , l d ) denotes the number of intervals at the lth level in each
dimension. Each entry is an integer. Similarly, j = (j 1 , . . . , j d ), with j t =
0, . . . , 2 l t , denotes the nodal ordering at the lth level in each dimension. Associated
with the multidimensional functions is the index set
B l =
j t = 1, . . . , 2 l t − 1, j t odd, t = 1, . . . , d, if l t > 0,
j t = 0, 1,
t = 1, . . . , d, if l t = 0 .
(9.3)