Multilevel, Extrapolation, and Sparse Grid Methods.

U. Rüde Institut für Informatik Technische Universität München
Arcisstr. 21
D-80290 Muenchen


Multigrid Methods are asymptotically optimal solvers for discretized partial differential equations (PDE). For the optimal solution of PDEs, however, the quality of the discretization is of the same importance as the speed of the algebraic solution process. Especially for high accuracy requirements, high order discretizations become increasingly attractive. We describe higher order techniques, like extrapolation and sparse grid combination that are particularly interesting in the context of multilevel algorithms, because they are based on discretizing the problems on grids with different mesh sizes. Classical Richardson extrapolation can be extended and generalized in many ways. One generalization is to consider the mesh widths in the different coordinate directions as distinct parameters. This leads to the so-called multivariate extrapolation and the combination technique.

Contributed July 30, 1993.