Sparse grids

We present a survey of the fundamentals and the applications of sparse grids, with a focus on the solution of partial differential equations (PDEs). The sparse grid approach, introduced in Zenger (1991), is based on a higher-dimensional multiscale basis, which is derived from a one-dimensional multi-scale basis by a tensor product construction. Discretizations on sparse grids involve $O(N \cdot (\log N)^{d-1})$ degrees of freedom only, where $d$ denotes the underlying problem's dimensionality and where $N$ is the number of grid points in one coordinate direction at the boundary. The accuracy obtained with piecewise linear basis functions, for example, is $O(N^{-2} \cdot (\log N)^{d-1})$ with respect to the…