The Sparse Grid metamodeling is a hierarchical Sparse Grid interpolation algorithm based on piecewise multilinear basis functions.
The first ingredient of a Sparse Grid method is a one-dimensional multilevel basis.
Piecewise linear hierarchical basis (from the level 0 to the level 3):

The calculation of coefficients values associated to a piecewise linear basis is hierarchical and obtained by the differences between the values of the objective function and the evaluation of the current Sparse Grid interpolation.
For a multi-dimensional problem, the Sparse Grid metamodeling is based on piecewise multilinear basis functions that are obtained by a sparse tensor product construction of one-dimensional multi-level basis.
Let denote a multi-index, where
is the problem dimension (number of input parameters) and
corresponds to the level in the
direction.
The generation of the Sparse Grid is obtained by the following tensor product:
Tensor product of linear basis functions for a two-dimensional problem:

To generate a new Sparse Grid , any Sparse Grid
that meets the order relation
must be generated before:
means:
with
and
For example, in two-dimensional problem, the generation of the grid required several steps:
Generation of
Generation of and
Generation of n and
The calculation of coefficients values associated to a piecewise multilinear basis is similar to the calculation of coefficients of linear basis: the coefficients are obtained by the differences between the values of the objective function on the new grid and the evaluation (of the same grid) with the current Sparse Grid interpolation (based on old grids).
you can observe for a higher-dimensional problem that not all input variables carry equal weight. A regular Sparse Grid refinement can lead to too many support nodes. This is why the Sparse Grid metamodeling uses a dimension-adaptive algorithm to automatically detect separability and which dimensions are the more or the less important ones to reduce computational effort for the objectives functions.
The hierarchical structure is used to obtain an estimate of the current approximation
error. This current approximation error is used to choose the relevant direction to refine
the Sparse Grids. If the approximation error has been found with Sparse Grid Wl, the next
iteration consists in the generation of new Sparse Grids obtained by incrementing of each
dimension level of (one by one) as far as possible: the refinement of
can generate two new Sparse Grids
and
(if the
and
already exist).

The Sparse Grid metamodeling stops automatically when the desired accuracy is reached or when the maximum depth is met in all directions (the maximum depth corresponds to the maximum number of hierarchical interpolation levels to compute: if the maximum depth is reached in one direction, the direction is not refined further).
The new generation of the Sparse Grid allows as many linear basis functions as there are points of discretization.

All Sparse Grids generated by the tensor product contain only one-point that allows refinement more locally.
Sparse grid metamodeling is more efficient with a more local refinement process that uses less design points, as well as, reaching the requested accuracy faster.
