A UNIDIRECTIONAL APPROACH FOR D-DIMENSIONAL FINITE ELEMENT METHODS 
                     OF HIGHER ORDER ON SPARSE GRIDS

                          Hans-Joachim Bungartz 
                        Institut f"ur Informatik
                     Technische Universit"at M"unchen
                       D-80290 M"unchen, Germany
                e-mail: bungartz@informatik.tu-muenchen.de

                                 Abstract

In the last years, sparse grids have turned out to be a very interesting
approach for the efficient iterative numerical solution of elliptic boundary
value problems. In comparison to standard (full grid) discretization schemes,
the number of grid points can be reduced significantly from O(N^d) to
O(N (log_2(N))^(d-1)) or even O(N) in the d-dimensional case, whereas the 
accuracy of the approximation to the finite element solution is only
slightly deteriorated: For piecewise d-linear basis functions, e. g., an
accuracy of the order O(N^(-2) (log_2(N))^(d-1)) with respect to the L_2-norm
and of the order O(N^(-1)) with respect to the energy norm has been shown.
Furthermore, regular sparse grids can be extended in a very simple and
natural manner to adaptive ones, which makes the hierarchical sparse grid
concept applicable to problems that require adaptive grid refinement, too.

Starting from d-dimensional basis functions that are created from the
one-dimensional ones by a tensor product approach, sparse grids allow the
formulation of unidirectional algorithms for partial differential equations
which are essentially independent of the number d of dimensions. Those 
unidirectional techniques are advantageous, since most of the algorithmic
development can be done in the (simple) one-dimensional situation, whereas
the generalization to d>1 just results in additional outer loops or further
levels of recursion.

Furthermore, it has been shown that sparse grids allow an accuracy of the
finite element solution of O(M^(-p)) with respect to the energy norm, where
M denotes the total number of unknowns involved in the given d-dimensional
problem, and p is the polynomial degree of the basis functions used. Because
of the accuracy's independence of the number d of dimensions, the sparse grid
concept looks quite promising for the construction of efficient high order
techniques in three or more dimensions.

In this paper, a unidirectional sparse grid Poisson solver for an arbitrary 
number d of dimensions and for various polynomial degrees p of the finite
element basis functions is presented, together with first numerical examples.
Combining the unidirectional sparse grid concept with higher order finite
elements, this algorithm can be seen as a step on the way to the implementation
of h-p-version-type finite element methods for arbitrary d on sparse grids.