In scientific computing, efficient discretization technqiues are of crucial importance. While a sophisticated a priori choice of grid patterns has a quite long tradition for the approximation, interpolation, and integration of functions, the hierarchical sparse grid concept was the first approach to combine such structural considerations with adaptive finite element discretizations for partial differential equations. The most important property of sparse grids is certainly the fact that the number of degrees of freedom necessary to achieve a certain given accuracy does not depend or depends only on very slightly on the problem's dimensionality d, which is advantageous especially for problems with large d.

In this text, we deal with both the theoretical and the algorithmic extension of the piecewise linear approach used so far to polynomial bases odf an arbitrary and varying degree. The construction of suitable hierarchical bases with just one degree of freedom per element and the generalization of the unidirectional sparse grid algorithms allow to combine the optimal complexity of the sparse grid approach with the advantages of both adaptive mesh refinement and higher order approximation.