Sparse grids are numerical techniques to represent, integrate or interpolate high dimensional functions. They were originally developed by the Russian mathematician Sergey A. Smolyak, a student of Lazar Lyusternik, and are based on a sparse tensor product construction. Computer algorithms for efficient implementations of such grids were later developed by Michael Griebel and Christoph Zenger.
Curse of dimensionality.
The standard way of representing multidimensional functions are tensor or full grids. The number of basis functions or nodes (grid points) that have to be stored and processed depend exponentially on the number of dimensions.
The curse of dimensionality is expressed in the order of the integration error that is made by a quadrature of level formula_1, with formula_2 points. The function has regularity formula_3, i.e. is formula_3 times differentiable. The number of dimensions is formula_5.
formula_6
Smolyak's quadrature rule.
Smolyak found a computationally more efficient method of integrating multidimensional functions based on a univariate quadrature rule formula_7. The formula_5-dimensional Smolyak integral formula_9 of a function formula_10 can be written as a recursion formula with the tensor product.
formula_11
The index to formula_12 is the level of the discretization. If a 1-dimension integration on level formula_13 is computed by the evaluation of formula_14 points, the error estimate for a function of regularity formula_3 will be
formula_16