Sparse grids are a numerical technique to represent, integrate or interpolate high dimensional functions. They were originally found by the Russianmathematician Smolyak. Computer algorithms for efficient implementations of such grids were later developed by Michael Griebel and Christoph Zenger. 2-dimensional renderings (ie. ... Leonhard Euler is considered by many people to be one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is mathematics. ...
Curse of dimension
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 exponential function is one of the most important functions in mathematics. ...
The curse of dimension is expressed in the order of the integration error that is made by a quadrature of level l, with Nl points. The function has regularity r, i.e. is r times differentiable. The number of dimensions is d.
Smolyak's quadrature rule
Smolyak found a computationally more efficient method of integrating multidimensional functions based on a univariate quadrature rule Q(1). The d-dimensional Smolyak integral Q(d)of a function f can be written as a recursion formula with the tensor product.
The index to Q is the level of the discretization. A 1-d integration on level i is computed by the evaluation of O(2i) points. The error estimate for a function of regularity r is:
References
Finite difference scheme on sparse grids
Visualization on sparse grids
CiteSeer: Adaptive Sparse Grids, M. Hegland
Datamining on sparse grids J.Garcke, M.Griebel (pdf)
For interpolation on sparsegrids, a hierarchy of basis functions is used, where some functions are defined on the entire grid.
The actual sparsegrid is created by removing the points that do not contribute to the the sparsegrid interpolation functions from the associated full grid (Figure 2).
Sparsegrids need only a negligible amount of memory compared with their associated full grids as shown in Table 1.
Sparsegrids are a numerical technique to represent, integrate or interpolate high dimensional functions.
For interpolation on sparsegrids, a hierarchy of basis functions is used, where some functions are defined on the entire grid.
The actual sparsegrid is created by removing the points that do not contribute to the the sparsegrid interpolation functions from the associated full grid (Figure 2).
Feeds |
Contact