Sparse Grid

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.

Example 5:  Interpolation with the Hierarchical Basis

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:

Example 6:  Tensor Product Approach to Generate the Piecewise Bilinear Basis Functions W2,0

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:

  1. Generation of

  2. Generation of and

  3. 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.


Release 18.2 - © ANSYS, Inc. All rights reserved.