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. Even with today's computational power it is not possible to process functions with more than 4 or 5 dimensions.
The curse of dimensionality is expressed in the order of the integration error that is made by a quadrature of level , with points. The function has regularity , i.e. is times differentiable. The number of dimensions is .
Smolyak's quadrature rule
Smolyak found a computationally more efficient method of integrating multidimensional functions based on a univariate quadrature rule . The -dimensional Smolyak integral of a function can be written as a recursion formula with the tensor product.
The index to is the level of the discretization. A integration on level is computed by the evaluation of points. The error estimate for a function of regularity is:
- A memory efficient data structure for regular sparse grids
- Code to generate (and pre-generated) nodes and weights for quadrature
- Finite difference scheme on sparse grids
- Visualization on sparse grids
- Datamining on sparse grids, J.Garcke, M.Griebel (pdf)
- Jochen Garcke:"Sparse Grids in a Nutshell" (pdf)
- Paul Constantine: "Experiences with Sparse Grids and Smolyak-type Approximations" (pdf)
- Christoph Zenger: "Sparse Grids" (pdf)
- Garcke, Jochen(Ed.) and Griebel, Michael (Ed.) : "Sparse Grids and Applications", Springer, ISBN 978-3-642-31702-6 (2013).
- J. Brumm and S. Scheidegger:"Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models",(2013) (pdf)
- "Quadrature on sparse grids"
|This mathematical analysis–related article is a stub. You can help Wikipedia by expanding it.|