Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation

Title Optimized wavelet approximation spaces for operator equations
Participant Stephan Knapek, Michael Griebel
Key words biorthogonal Wavelets, multilevel methods, optimized approximation spaces, sparse grids, norm equivalences, subspace splittings, partial differential equations, integral equations, elliptic problems, hyperbolic crosspoints, tensor-products
Description We are concerned with the construction of optimized grids and approximation spaces for elliptic pseudodifferential operators of arbitrary order. Based on the framework of tensor-product biorthogonal wavelet bases and stable subspace splittings, we construct operator adapted finite element subspaces with less dimension than the standard full grid spaces that keep the approximation order of the standard full grid spaces provided that certain additional regularity assumptions on the solution are fulfilled. Specifically for operators of positive order, the dimension is
independent of the dimension n of the problem compared to
for the full grid space. Also, for operators of negative order the overall complexity is significantly in favor of the new approximation spaces. We give complexity estimates for the case of continuous linear information.We show these results in a constructive manner by proposing a finite element method together with optimal preconditioning. The results are of special importance for problems in higher dimensions, where a straightforward use of the full grid approximation spaces is prohibitive. This idea has been well known for some time in approximation and interpolation theory and attracted much attention in last time. Note that this construction of approximation spaces (i.e., the selection of subspaces) hinges on the additional freedom that is provided by the tensor-product ansatz and on additional regularity requirements. The resulting sequence of grid points and supports has also been used successfully in connection with different hierarchical basis functions, for example prewavelets and higher order splines. We extend the ideas to pseudodifferential operators of arbitrary order and to approximation spaces spanned by biorthogonal wavelet systems. We base the construction of approximation spaces on the H^s-norm. This enables us to define optimized approximation spaces for elliptic operators acting on arbitrary H^s spaces. In the construction procedure of the approximation spaces there is a need for the decoupling of the subspaces arising from the tensor-product ansatz and semicoarsing in coordinate directions. Here we rely directly on norm estimates and norm equivalences that allow us to decouple the subspaces and moreover ensure the stability of the resulting subspace splittings. Hence norm equivalences are not only important for preconditioning, but can also be used as a source of information for discretization and subspace selection. The theory covers elliptic boundary value problems as well as boundary integral equations.
A special case of the spaces defined is the sparse grid space (or hyperbolic crosspoints) with tensor-product biorthogonal wavelets. See the next Figure for the grid points of a full and a sparse grid.
The dimension of the considered approximation spaces is significantly smaller than that of the full grid approximation space. See the next Figures.
Details can be found in the papers.
  • H.-J. Bungartz, M. Griebel: A note on the complexity of solving Poisson's equation for spaces of bounded mixed derivatives, J. Complexity, 1998, submitted.
  • M. Griebel, S. Knapek: Optimized approximation spaces for operator equations , Report, SFB 256, University Bonn, 1998.
  • M. Griebel, S. Knapek, T. Schiekofer: Galerkin discretizations of pseudodifferential operators using wavelets of tensor-product type: Dimension reduction and compression, in preparation.
  • M. Griebel, P. Oswald, T. Schiekofer: Sparse grids for boundary integral equations, Numerische Math. (submitted), 1998.
Related projects

Stephan Knapek
Last modified: Thu Aug 6