Applied Mathematics Seminar

Sparse grid methods

Speaker: Prof. Dr. Michael Griebel
Institut für Numerische Simulation Rheinische Friedrich-Wilhelms-Universität Bonn

Date: Thursday March 3rd
Time: 11am
Room: RC-4082

Abstract: The numerical treatment of high(er) dimensional problems suffers in
general from the so-called curse of dimensionality. In special cases, i.e.
for special function classes, this exponential dependence of $O(n^{-r/d})$ of
the achieved accuracy on the invested work $n$ can be substantially reduced.
Here, $r$ denotes smoothness and $d$ dimensionality. This is e.g. the case
for spaces of functions with bounded mixed derivatives. The associated
numerical schemes involve a series expansion in a multiscale basis for the
one-dimensional problem. Then, a product construction and a proper truncation
of the resulting d-dimensional expansion result in a so-called sparse grid
approximation. Here, depending on the respective problem and the
1-dimensional multiscale basis used, a variety of algorithms for higher
dimensional problems result which allow to break the curse of dimensionality,
at least to some extent, and result in complexities of the order $O(n^{-r}
log(n)^{\alpha(d)}$. In special cases even $\alpha(d)=0$ can be achieved.
This is possible if the error is measured in the $H_1$ seminorm or if the
different dimensions as well as their interactions are not eqally
important and dimension-adaptive strategies are used.
The constant in these order estimates, however, is still dependent on $d$. It
also reflects subtile details of the implementation of the respective
numerical scheme.

We discuss such sparse grid algorithms for the numerical
treatment of integration problems, partial differential equations and data
analysis.