A note on the complexity of solving Poisson's equation for spaces of bounded mixed derivatives (Q1974571)

This paper studies the solution of the Poisson equation in a \(d\)-dimensional cube using a hierarchical, tensor product finite element basis on sparse grids. Whereas on earlier sparse grids the number of unknowns (and operations) was \(O(h^{-1}|\log h|^{d-1})\) guaranteeing an accuracy of \(O(h)\), now an even sparser grid is proposed (thanks to an explicit solution of a corresponding optimization problem) leading to a discrete problem with \(O(h^{-1})\) unknowns which can be solved with a multilevel preconditioner based on prewavelets [constructed by \textit{M. Griebel} and \textit{P. Oswald}, Adv. Comput. Math. 4, No.~1-2, 171-206 (1995; Zbl 0826.65099)] in \(O(h^{-1})\) operations. This approach gives an accuracy of \(O(h)\) in the energy norm, assuming the solution of the original continuous problem to have bounded mixed derivatives (in the \(L_\infty\)- or \(L_2\)-norm) up to order \(2d\).