Editing Sparse grid

'''Sparse grids''' are numerical techniques to represent, integrate or interpolate high [[dimension]]al functions. They were originally developed by the [[Russia]]n [[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 [[exponential function|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 <math>l</math>, with <math>N_{l}</math> points. The function has regularity <math>r</math>, i.e. is <math>r</math> times differentiable. The number of dimensions is <math>d</math>.

<math>|E_l| = O(N_l^{-\frac{r}{d}})</math>

== Smolyak's quadrature rule ==
Smolyak found a computationally more efficient method of integrating multidimensional functions based on a [[univariate]] quadrature rule <math>Q^{(1)}</math>. The <math>d</math>-dimensional Smolyak integral <math>Q^{(d)}</math> of a function <math>f</math> can be written as a recursion formula with the [[tensor product]].

<math>Q_l^{(d)} f = \left(\sum_{i=1}^l \left(Q_i^{(1)}-Q_{i-1}^{(1)}\right)\otimes Q_{l-i+1}^{(d-1)}\right)f</math>

The index to <math>Q</math> is the level of the [[discretization]]. If a 1-dimension integration on level <math>i</math> is computed by the evaluation of <math>O(2^{i})</math> points, the error estimate for a function of regularity <math>r</math> will be
<math>|E_l| = O\left(N_l^{-r}\left(\log N_l\right)^{(d-1)(r+1)}\right)</math>

== Further reading ==
*{{cite journal |first1=J. |last1=Brumm |first2=S. |last2=Scheidegger |title=Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models |journal=[[Econometrica]] |volume=85 |issue=5 |year=2017 |pages=1575–1612 |doi=10.3982/ECTA12216 |url=https://www.zora.uzh.ch/id/eprint/142226/1/Scheidegger_Econometrica%24ECTA12216.pdf }}
*{{cite book |chapter-url=https://ins.uni-bonn.de/media/public/publication-media/sparse_grids_nutshell_code.pdf |first=Jochen |last=Garcke |chapter=Sparse Grids in a Nutshell |editor-last=Garcke |editor-first=Jochen |editor2-last=Griebel |editor2-first=Michael |editor2-link=Michael Griebel |title=Sparse Grids and Applications |publisher=Springer |isbn=978-3-642-31702-6 |year=2012 |pages=57–80 }}
*{{cite book |chapter-url=https://www5.in.tum.de/pub/zenger91sg.pdf |first=Christoph |last=Zenger |chapter=Sparse Grids |editor-first=Wolfgang |editor-last=Hackbusch |title=Parallel Algorithms for Partial Differential Equations |location= |publisher=Vieweg |year=1991 |pages=241–251 |isbn=3-528-07631-3 }}

== External links ==
* [http://www.lrr.in.tum.de/~murarasu/ppopp027s-murarasu.pdf A memory efficient data structure for regular sparse grids]
* [http://wissrech.iam.uni-bonn.de/research/projects/zumbusch/fd.html Finite difference scheme on sparse grids]
* [https://web.archive.org/web/20120219044130/http://cumbia.informatik.uni-stuttgart.de/ger/research/fields/recent/sparse/ Visualization on sparse grids]
* [http://wissrech.iam.uni-bonn.de/research/pub/garcke/kdd.pdf Datamining on sparse grids,  J.Garcke, M.Griebel (pdf)]

{{Mathanalysis-stub}}
[[Category:Numerical analysis]]