Sparse grid
Encyclopedia
Sparse grids are numerical techniques to represent, integrate or interpolate high dimension
al functions. They were originally found by the Russia
n mathematician
Smolyak 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 dimension 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 
.
. 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:
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
al functions. They were originally found by the Russia
Russia
Russia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...
n mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Smolyak and are based on a sparse tensor product construction. Computer algorithms for efficient implementations of such grids were later developed by Michael Griebel
Michael Griebel
Michael Griebel is a German mathematician. His research focus lies on scientific computing, and he helped develop computer algorithms for Sparse Grids....
and Christoph Zenger
Christoph Zenger
Christoph Zenger is a German mathematician.-Career:Born in Lindau, Zenger studied physics at the Ludwig Maximilian University of Munich and did a doctorate in mathematics in 1967. In 1973 he did his habilitation in mathematics and in 1977 he became professor of mathematics at Technical University...
.
Curse of dimensionalityCurse of dimensionalityThe curse of dimensionality refers to various phenomena that arise when analyzing and organizing high-dimensional spaces that do not occur in low-dimensional settings such as the physical space commonly modeled with just three dimensions.There are multiple phenomena referred to by this name in...
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 exponentiallyExponential function
In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...
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
, 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: