Volume 6, pp. 63-77, 1997.

A multigrid algorithm for higher order finite elements on sparse grids

Hans-Joachim Bungartz

Abstract

For most types of problems in numerical mathematics, efficient discretization techniques are of crucial importance. This holds for tasks like how to define sets of points to approximate, interpolate, or integrate certain classes of functions as accurate as possible as well as for the numerical solution of differential equations. Introduced by Zenger in 1990 and based on hierarchical tensor product approximation spaces, sparse grids have turned out to be a very efficient approach in order to improve the ratio of invested storage and computing time to the achieved accuracy for many problems in the areas mentioned above. Concerning the sparse grid finite element discretization of elliptic partial differential equations, recently, the class of problems that can be tackled has been enlarged significantly. First, the tensor product approach led to the formulation of unidirectional algorithms which are essentially independent of the number $d$ of dimensions. Second, techniques for the treatment of the general linear elliptic differential operator of second order have been developed, which, with the help of domain transformation, enable us to deal with more complicated geometries, too. Finally, the development of hierarchical polynomial bases of piecewise arbitrary degree $p$ has opened the way to a further improvement of the order of approximation. In this paper, we discuss the construction and the main properties of a class of hierarchical polynomial bases and present a symmetric and an asymmetric finite element method on sparse grids, using the hierarchical polynomial bases for both the approximation and the test spaces or for the approximation space only, resp., with standard piecewise multilinear hierarchical test functions. In both cases, the storage requirement at a grid point does not depend on the local polynomial degree $p$, and $p$ and the resulting representations of the basis functions can be handled in an efficient and adaptive way. An advantage of the latter approach, however, is the fact that it allows the straightforward implementation of a multigrid solver for the resulting system which is discussed, too.

Full Text (PDF) [1 MB], BibTeX

Key words

sparse grids, finite element method, higher order elements, multigrid methods.

AMS subject classifications

35J05, 65N15, 65N30, 65N55.