Space-time approximation with sparse grids

In this article we introduce approximation spaces, especially suited for the approximation of solutions of 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 so-called space-time 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(Nd) degrees of freedom for the discretization of the whole space-time problem. But they provide the same approximation rate as classical space-time finite element spaces which need O(Nd+1) degrees of freedoms. This makes these approximation spaces well suited for conventional parabolic and time-dependent optimization problems. We analyze the approximation properties and the dimension of these sparse grid space-time 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. ne grid points by a least squares approach. This way we obtain an algebraic hierarchical basis for the spatial domain which we then use in our space-time sparse grid approach. We give numerical results on the convergence rate of the interpolation error of these spaces for various space-time problems with two spatial dimensions. Implementational issues, data structures, and questions of adaptivity also are addressed to some extent.