[1] 
M. Griebel, D. Oeltz, and P. Vassilevski.
Spacetime approximation with sparse grids.
SIAM J. Sci. Comput., 28(2):701727, 2005.
Also as Preprint No. 222, SFB 611, University of Bonn. [ bib  .pdf 1 ] In this report we introduce approximation spaces for parabolic problems which are based on the tensor product construction of a multiscale basis in space and a multiscale basis in time. Proper truncation then leads to socalled spacetime sparse grid spaces. For a uniform discretization of the spatial space of dimension d with O(N^d) degrees of freedom, these spaces involve for d > 1 also only O(N^d) degrees of freedom for the discretization of the whole spacetime problem. But they provide the same approximation rate as classical spacetime Finite Element spaces which need O(N^(d+1)) degrees of freedoms. This makes these approximation spaces well suited for conventional parabolic and for timedependent optimization problems. We analyze the approximation properties and the dimension of these sparse grid spacetime spaces for general stable multiscale bases. We then restrict ourselves to an interpolatory multiscale basis, i.e. a hierarchical basis. Here, to be able to handle also complicated spatial domains Omega, we construct the hierarchical basis from a given spatial Finite Element basis as follows: First we determine coarse grid points recursively over the levels by the coarsening step of the algebraic multigrid method. Then, we derive interpolatory prolongation operators between the respective coarse and fine grid points by a least square approach. This way we obtain an algebraic hierarchical basis for the spatial domain which we then use in our spacetime sparse grid approach. We give numerical results on the convergence rate of the interpolation error of these spaces for various spacetime problems with two spatial dimensions. Also implementational issues, data structures and questions of adaptivity are addressed to some extent.
