A Multigrid Algorithm for Higher Order Finite Elements on Sparse Grids

Hans-Joachim Bungartz

Institut für Informatik
Technische Universität München
D - 80290 München


Efficient discretization techniques are of crucial importance for most types of problems in numerical mathematics, starting from tasks like how to define sets of points to approximate, interpolate, or integrate certain classes of functions as good as possible, up to the numerical solution of differential equations. Introduced 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 the number of invested degrees of freedom or variables on the one side and the achieved accuracy on the other side for many problems in the areas mentioned above.

Concerning the sparse grid finite element discretization of elliptic partial differential equations, the class of problems that can be tackled has been enlarged significantly in the last years. 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 contribution, we present a symmetric and an asymmetric variant of the d-dimensional higher order 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. For both algorithms, 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. The latter approach, however, allows the straightforward implementation of a multigrid solver. We discuss the approximation qualities of both variants and the convergence behaviour of the multigrid algorithm, and we give numerical examples.


[1] I. Babuska and M. Suri, The p- and h-p-versions of the finite element method: An overview, Comput. Methods Appl. Mech. Engrg., 80 (1990), pp. 5-26.
[2] H.-J. Bungartz, Concepts for higher order finite elements on sparse grids, in Proceedings of the Third Int. Conf. on Spectral and High Order Methods, Houston, Houston Journal of Mathematics, L. R. Scott and A. V. Ilin, eds., pp. 159-170, 1996.
[3] H.-J. Bungartz and T. Dornseifer, Sparse grids: Recent developments for partial differential equations, to be published.
[4] H.-J. Bungartz, M. Griebel, and U. Rüde, Extrapolation, combination, and sparse grid techniques for elliptic boundary value problems, Comput. Methods Appl. Mech. Engrg., 116 (1994), pp. 243-252.
[5] T. Dornseifer and C. Pflaum, Discretization of elliptic differential equations on curvilinear bounded domains with sparse grids, Computing, 56 (1996), pp. 197-214.
[6] M. Griebel and P. Oswald, On additive Schwarz preconditioners for sparse grid discretizations, Numer. Math., 66 (1994), pp. 449 ff.
[7] C. Zenger, Sparse grids, in Parallel Algorithms for Partial Differential Equations: Proceedings of the Sixth GAMM-Seminar, Kiel, 1990, Notes on Numerical Fluid Mechanics 31, W. Hackbusch, ed., Vieweg, Braunschweig, 1991.