On a multilevel preconditioner and its condition numbers for the discretized Laplacian on full and sparse grids in higher dimensions

We first discretize the d-dimensional Laplacian in (0, 1) d for varying d on a full uniform grid and build a new preconditioner that is based on a multilevel generating system. We show that the resulting condition number is bounded by a constant that is independent of both, the level of discretization J and the dimension d. Then, we consider so-called sparse grid spaces, which offer nearly the same accuracy with far less degrees of freedom for function classes that involve bounded mixed derivatives. We introduce an analogous multilevel preconditioner and show that it possesses condition numbers which are at least as good as these of the full grid case. In fact, for sparse grids we even observe falling condition numbers with rising dimension in our numerical experiments. Furthermore, we discuss the cost of the algorithmic implementations. It is linear in the degrees of freedom of the respective multilevel generating system. For completeness, we also consider the case of a sparse grid discretization using prewavelets and compare its properties to those obtained with the generating system approach.