Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation

  author = {Hans-Joachim Bungartz and Michael Griebel},
  title = {Sparse grids},
  journal = {Acta Numerica},
  volume = {13},
  pages = {1-123},
  year = {2004},
  pdf = { 1},
  abstract = {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 multiscale basis by a tensor product
		  construction. Discretizations on sparse grids involve $O(N
		  (\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 piece-wise linear
		  basis functions, for example, is $O(N^{-2} (\log N)^{d-1})$
		  with respect to the $L_2$- and $L_\infty$-norm, if the
		  solution has bounded second mixed derivatives. This way,
		  the curse of dimensionality, i.e., the exponential
		  dependence $O(N^d)$ of conventional approaches, is overcome
		  to some extent. For the energy norm, only $O(N)$ degrees of
		  freedom are needed to give an accuracy of $O(N^{-1})$. This
		  is why sparse grids are especially well-suited for problems
		  of very high dimensionality.
		  The sparse grid approach can be extended to nonsmooth
		  solutions by adaptive refinement methods. Furthermore, it
		  can be generalized from piecewise linear to higher-order
		  polynomials. Also, more sophisticated basis functions like
		  interpolets, prewavelets, or wavelets can be used in a
		  straightforward way.
		  We describe the basis features of sparse grids and report
		  the results of various numerical experiments for the
		  solution of elliptic PDEs as well as for other selected
		  problems such as numerical quadrature and data mining.},
  annote = {article,1145,amamef,C2,data,ALM}