Sparse grid explained

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, Christoph Zenger, and Dirk Pflüger.

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

, with

N_l

points. The function has regularity

, i.e. is

times differentiable. The number of dimensions is

|E_l|=

-	r
	d

O(N

)

Smolyak's quadrature rule

Smolyak found a computationally more efficient method of integrating multidimensional functions based on a univariate quadrature rule

Q⁽¹⁾

. The

-dimensional Smolyak integral

Q^(d)

of a function

can be written as a recursion formula with the tensor product.

	(d)
Q
	l

	l
\left(\sum
	i=1

	(1)
\left(Q
	i

	(1)
-Q
	i-1

\right) ⊗

	(d-1)
Q
	l-i+1

\right)f

The index to

is the level of the discretization. If a 1-dimension integration on level

is computed by the evaluation of

O(2ⁱ)

points, the error estimate for a function of regularity

will be

|E_l|=

	-r
O\left(N
	l

\left(log

	(d-1)(r+1)
N
	l\right)

\right)

Sparse grid explained

Curse of dimensionality

Smolyak's quadrature rule

Further reading

External links