Applied Mathematics Seminar


Thursday, 3rd March 2005

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