Sparse grids are a numerical technique to represent, integrate or interpolate high dimensional functions. They were originally found by the Russian mathematician Smolyak. Computer algorithms for efficient implementations of such grids were later developed by Michael Griebel and Christoph Zenger.

Curse of dimension

---

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. Even with today's computational power it is not possible to process functions with more than 4 or 5 dimensions.

The curse of dimension is expressed in the order of the integration error that is made by a quadrature of level l, with N_l points. The function has regularity r, i.e. is r times differentiable. The number of dimensions is d.

$|E\_l|\; =\; O(N\_l^\{-\backslash frac\{r\}\{d\}\})$

Smolyak's quadrature rule

---

Smolyak found a computationally more efficient method of integrating multidimensional functions based on a univariate quadrature rule Q⁽¹⁾. The d-dimensional Smolyak integral Q^(d)of a function f can be written as a recursion formula with the tensor product.

$Q\_l^\{(d)\}\; f\; =\; \backslash left(\backslash sum\_\{i=0\}^l\; \backslash left(Q\_i^\{(1)\}-Q\_\{i-1\}^\{(1)\}\backslash right)\backslash otimes\; Q\_\{l-i\}^\{(d-1)\}\backslash right)f$

The index to Q is the level of the discretization. A 1-d integration on level i is computed by the evaluation of O(2ⁱ) points. The error estimate for a function of regularity r is:

$|E\_l|\; =\; O\backslash left(N\_l^\{-r\}\backslash left(\backslash log\; N\_l\backslash right)^\{(d-1)(r+1)\}\backslash right)$

References

---

• Finite difference scheme on sparse grids
• Visualization on sparse grids
• CiteSeer: Adaptive Sparse Grids, M. Hegland
• Datamining on sparse grids J.Garcke, M.Griebel (pdf)

Numerical analysis