Adaptive wavelet algorithms for elliptic PDE's on product domains

With standard isotropic approximation by (piecewise) polynomials of fixed order in a domain $D\subset \mathbb{R}^d$, the convergence rate in terms of the number $N$ of degrees of freedom is inversely proportional to the space dimension $d$. This so-called curse of dimensionality can be circumvented by applying sparse tensor product approximation, when certain high order mixed derivatives of the approximated function happen to be bounded in $L_2$. It was shown by Nitsche (2006) that this regularity constraint can be dramatically reduced by considering best $N$-term approximation from tensor product wavelet bases. When the function is the solution of some well-posed operator equation, dimension independent approximation rates can be practically realized in linear complexity by adaptive wavelet algorithms, assuming that the infinite stiffness matrix of the operator with respect to such a basis is highly compressible. Applying piecewise smooth wavelets, we verify this compressibility for general, non-separable elliptic PDEs in tensor domains. Applications of the general theory developed include adaptive Galerkin discretizations of multiple scale homogenization problems and of anisotropic equations which are robust, i.e., independent of the scale parameters, resp. of the size of the anisotropy.