Sparse grid

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 ${\displaystyle l}$ , with ${\displaystyle N_{l}}$  points. The function has regularity ${\displaystyle r}$ , i.e. is ${\displaystyle r}$  times differentiable. The number of dimensions is ${\displaystyle d}$ .

${\displaystyle |E_{l}|=O(N_{l}^{-{\frac {r}{d}}})}$ 

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

${\displaystyle 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}$ 

The index to ${\displaystyle Q}$  is the level of the discretization. If a 1-dimension integration on level ${\displaystyle i}$  is computed by the evaluation of ${\displaystyle O(2^{i})}$  points, the error estimate for a function of regularity ${\displaystyle r}$  will be ${\displaystyle |E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)}$ 

• Brumm, J.; Scheidegger, S. (2017). "Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models" (PDF). Econometrica. 85 (5): 1575–1612. doi:10.3982/ECTA12216.
• Garcke, Jochen (2012). "Sparse Grids in a Nutshell" (PDF). In Garcke, Jochen; Griebel, Michael (eds.). Sparse Grids and Applications. Springer. pp. 57–80. ISBN 978-3-642-31702-6.
• Zenger, Christoph (1991). "Sparse Grids" (PDF). In Hackbusch, Wolfgang (ed.). Parallel Algorithms for Partial Differential Equations. Vieweg. pp. 241–251. ISBN 3-528-07631-3.

• A memory efficient data structure for regular sparse grids
• Finite difference scheme on sparse grids
• Visualization on sparse grids
• Datamining on sparse grids, J.Garcke, M.Griebel (pdf)