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, tensorproducts

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 tensorproduct 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
O(2^J)
independent of the dimension n of the problem compared to
O(2^(Jn))
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 tensorproduct 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^snorm.
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 tensorproduct 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 tensorproduct 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.

Bibliography

 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 tensorproduct 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

