Report 2007-06

Multilevel frames for sparse tensor product spaces

R. Harbrecht, R. Schneider and C. Schwab

Abstract: For Au=f with an elliptic differential operator $A:\mathcal{H}\rightarrow\mathcal{H}'$ and stochastic data f, the m-point correlation function ${\mathcal M}^m u$ of the random solution u satisfies a deterministic, hypoelliptic equation with the m-fold tensor product operator $A^{(m)}$ of $A$. Sparse tensor products of hierarchic FE-spaces in $\mathcal{H}$ are known to allow for approximations to ${\mathcal M}^m u$ which converge at essentially the rate as in the case m=1, i.e. for the deterministic problem. They can be realized by wavelet-type FE bases [28]. If wavelet bases are not available, we show here how to achieve log-linear complexity computation of sparse approximations of ${\mathcal M}^m u$ for Galerkin discretizations of A by multilevel frames such as BPX or other multilevel preconditioners of any standard FEM approximation for A. Numerical examples illustrate feasibility and scope of the method.

Paper: Available as PDF (231 KB) or as hardcopy to order reports@sam.math.ethz.ch.