1 Introduction to Spectral Methods for Uncertainty Quantification
23
Algorithm 2 NISP algorithm
1 Choose M samples of the germ ξ (m) ∈ Ξ with dimension N . The sampling strategy depends
on step 4.
2 Compute the M fields K (m) (x, ξ ) using the truncated KL expansions in N terms.
3 Compute M realisations U (m) = U(x, ξ (m) ).
4 Find the coefficients of the spectral expansion, i.e. solve Eq. (1.19).
Algorithm 2. The most straightforward way to evaluate the integral in Eq. (1.19) is
through the MC approach. In order to do this, we impose w m = 1 for all m and
sample ξ (m) , randomly. The strength of the MC quadrature approach is that it is not
sensitive to the dimension of the stochastic space. This means that the computational
cost will always be similar. The drawback is that the convergence is very slow,
approximately equal to 1/
√
M; see [13]. Therefore it requires a very large number
of realisations to be unrolled. Nevertheless, there exist improved sampling strategies
that one may employ to generate the M sample sets ξ (m) and that allows to increase
the convergence rate.
Techniques, such as quasi-MC sampling and Latin-hypercube sampling (LHS)
[9, 13], use the same unitary weights as MC methods, but the quadrature points are
chosen in a deterministic way and not sampled randomly. However, these techniques
are affected by the curse of dimensionality, as they depend on the dimension of the
germ, and, as the stochastic dimension increases, their cost increases exponentially.
The LHS consists in forcing the sampler to draw the ξ (m) from equiprobable
bins, in the parameter range. This yields to the construction of a Latin square grid,
or a hypercube, if the stochastic space is multidimensional. In the hypercube there
is one, and only one, sample along each axis-aligned hyperplane containing it. This
LHS strategy allows to generate a near-random sample set of a multidimensional
stochastic space.
Another way of computing the integral in Eq. (1.19) is using a Gauss quadrature
formula where the samples ξ (m) and the weights w m are selected deterministically.
Generally, this yields a much faster convergence rate than a MC quadrature.
However, M is strictly related to the dimension of the stochastic space, and, due to
the curse of dimensionality, M grows exponentially as the dimension of Ξ increases.
Of course, there exist ways to overcome this issue and to reduce the number of
quadrature points. These techniques are called sparse Gauss quadrature formulae
[9]. Another drawback of Gauss formulae is that the set of points and weights for
a quadrature of degree N q is not contained in the same set of a N q + 1-degree
quadrature. This means that all the new sets of points must be computed, if a more
accurate quadrature formula is needed. Again, there are techniques, for instance,
adaptive Gauss quadrature, that helps avoiding this by recycling the quadrature
points. See [9, 14] for a discussion on sparse and adaptive Gaussian quadrature.
23
Algorithm 2 NISP algorithm
1 Choose M samples of the germ ξ (m) ∈ Ξ with dimension N . The sampling strategy depends
on step 4.
2 Compute the M fields K (m) (x, ξ ) using the truncated KL expansions in N terms.
3 Compute M realisations U (m) = U(x, ξ (m) ).
4 Find the coefficients of the spectral expansion, i.e. solve Eq. (1.19).
Algorithm 2. The most straightforward way to evaluate the integral in Eq. (1.19) is
through the MC approach. In order to do this, we impose w m = 1 for all m and
sample ξ (m) , randomly. The strength of the MC quadrature approach is that it is not
sensitive to the dimension of the stochastic space. This means that the computational
cost will always be similar. The drawback is that the convergence is very slow,
approximately equal to 1/
√
M; see [13]. Therefore it requires a very large number
of realisations to be unrolled. Nevertheless, there exist improved sampling strategies
that one may employ to generate the M sample sets ξ (m) and that allows to increase
the convergence rate.
Techniques, such as quasi-MC sampling and Latin-hypercube sampling (LHS)
[9, 13], use the same unitary weights as MC methods, but the quadrature points are
chosen in a deterministic way and not sampled randomly. However, these techniques
are affected by the curse of dimensionality, as they depend on the dimension of the
germ, and, as the stochastic dimension increases, their cost increases exponentially.
The LHS consists in forcing the sampler to draw the ξ (m) from equiprobable
bins, in the parameter range. This yields to the construction of a Latin square grid,
or a hypercube, if the stochastic space is multidimensional. In the hypercube there
is one, and only one, sample along each axis-aligned hyperplane containing it. This
LHS strategy allows to generate a near-random sample set of a multidimensional
stochastic space.
Another way of computing the integral in Eq. (1.19) is using a Gauss quadrature
formula where the samples ξ (m) and the weights w m are selected deterministically.
Generally, this yields a much faster convergence rate than a MC quadrature.
However, M is strictly related to the dimension of the stochastic space, and, due to
the curse of dimensionality, M grows exponentially as the dimension of Ξ increases.
Of course, there exist ways to overcome this issue and to reduce the number of
quadrature points. These techniques are called sparse Gauss quadrature formulae
[9]. Another drawback of Gauss formulae is that the set of points and weights for
a quadrature of degree N q is not contained in the same set of a N q + 1-degree
quadrature. This means that all the new sets of points must be computed, if a more
accurate quadrature formula is needed. Again, there are techniques, for instance,
adaptive Gauss quadrature, that helps avoiding this by recycling the quadrature
points. See [9, 14] for a discussion on sparse and adaptive Gaussian quadrature.