Fast computation of adaptive wavelet expansions

In this paper we describe and analyze an algorithm for the fast computation of sparse wavelet coefficient arrays typically arising in adaptive wavelet solvers. The scheme improves on an earlier version from Dahmen et al. (Numer. Math. 86, 49-101, 2000) in several respects motivated by recent developments of adaptive wavelet schemes. The new structure of the scheme is shown to enhance its performance while a completely different approach to the error analysis accommodates the needs put forward by the above mentioned context of adaptive solvers. The results are illustrated by numerical experiments for one and two dimensional examples.