SG++

Combination technique functionality.

The combination technique is an older variant of sparse grids which only allows dimensional, but not spatial adaptivity. However, a central advantage is that global interpolation and quadrature schemes can be used, e.g. polynomial interpolation. This allows for high orders of convergence when using sufficiently smooth functions.

The functionality of the module includes

We will introduce some basic terminology and conventions here. For usage and more details on features, please refer to usage examples (C++) and usage examples (Python).

The combination technique is an abstract scheme to combine one-dimensional numeric (linear) operations into a multi-dimensional operation. It provides a far better tradeoff between grid points and accuracy than working on a single regular/full grid \(X^{(1)} \times \ldots \times X^{(d)}\). For each dimension \(k \in \{1, \ldots, d\}\), the combination technique uses a sequence \((X^{(i)}_l)_{l \in \mathbb{N}_0}\) of 1D-grids of increasing size. The index \(l\) is also called the level of the grid. Unlike many papers, the level \(l\) starts from zero in this implementation.

The combination technique evaluates a given function on multiple (rather small) regular/full grids \(X_l := X^{(1)}_{l_1} \times \ldots \times X^{(d)}_{l_d}, l \in I \subseteq \mathbb{N}_0^d\). Here, \(l\) is a multi-index which is also called level of the (multi-dimensional) grid. \(I\) is the set of multi-indices of levels that corresponds to the regular/full grids that are evaluated. It must satisfy \(\forall l \in I: \forall j \in \mathbb{N}_0: ((\forall i \in \{1, \ldots, d\}: j_i \leq l_i) \Rightarrow j \in I)\). The results of all evaluated grids are combined to obtain a more precise numeric result. When we speak of adding levels, we mean inserting a level multi-index into \(I\) and incorporating the result of the evaluation on the added regular/full grid into the numerical approximation.

Standard approximations indicate that level multi-indices with a higher sum of their components are potentially less important. For \(q \in \mathbb{N}_0\), this yields the set \(I = \{l \in \mathbb{N}_0^d \mid l_1 + \ldots + l_d \leq q\}\) of regular levels. Often, it is better to choose the set of levels adaptively. This module provides such adaption algorithms; they also work in parallel.

The combigrid module separates operators and grid points. For example, the quadrature operation computes its quadrature weights by integrating Lagrange polynomials on grid that you choose for it. If you choose a sequence of points for the first dimension, you also have to choose \(|X^{(1)}_l|\) for all \(l \in \mathbb{N}_0\), i.e. the number of grid points per level, which is also referred to as the growth of the (number of) grid points. It is generally advisable that the grid points are nested, i.e. \(X^{(i)}_0 \subseteq X^{(i)}_1 \subseteq X^{(i)}_2 \subseteq \ldots\), which may require a specific growth of the grid points. To simplify the decisions to be made, the combigrid module already provides suitable combinations of grid points, growths and operators.

The main functionality of the module is containted in

  • interface classes that try to hide the the computation chain
  • grid point and growth classes
  • 1D-operator classes
  • storage classes that store computed function values
  • FullGrid*Evaluator, which takes the grid points, operators and a storage to compute a value on a regular/full grid \(X_l\)
  • CombigridEvaluator, which uses FullGridTensorEvaluator to perform the numeric computation on different regular/full grids and combines the obtained values
  • level manager classes that provide functionality to add a set of levels to the CombigridEvaluator, e.g. regular levels or adaptively generated levels.

To use the UQ methods of the combigrid module, Dakota is required as a dependency. Integrate Dakota