Supriya Ghosh (Editor)

Sparse grid

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Sparse grid wwwiansunistuttgartdespinterphelpimagesex

Discretization of elliptic differential equations using sparse grids cristoph pflaum


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 and Christoph Zenger.

Contents

Sparse grid Linear basis functions Sparse Grid Interpolation Toolbox

Broke one sparse grids


Curse of dimensionality

Sparse grid cmpgrids Sparse Grid Interpolation Toolbox

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.

Sparse grid Parallel Adaptive Sparse Grids

The curse of dimension is expressed in the order of the integration error that is made by a quadrature of level l , with N l points. The function has regularity r , i.e. is r times differentiable. The number of dimensions is d .

Sparse grid Parallel Adaptive Sparse Grids

| E l | = O ( N l − r d )

Smolyak's quadrature rule

Sparse grid Parallel Adaptive Sparse Grids

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.

Sparse grid Sparse Grid Algorithms

Q l ( d ) f = ( ∑ i = 1 l ( Q i ( 1 ) − Q i − 1 ( 1 ) ) ⊗ Q l − i + 1 ( d − 1 ) ) f

The index to Q is the level of the discretization. A 1 − d integration on level i is computed by the evaluation of O ( 2 i ) points. The error estimate for a function of regularity r is:

| E l | = O ( N l − r ( log ⁡ N l ) ( d − 1 ) ( r + 1 ) )

References

Sparse grid Wikipedia
(Text) CC BY-SA