Fast evaluation of nonlinear functionals of tensor product wavelet expansions

Abstract For a nonlinear functional f, and a function u from the span of a set of tensor product interpolets, it is shown how to compute the interpolant of f (u) from the span of this set of tensor product interpolets in linear complexity, assuming that the index set has a certain multiple tree structure. Applications are found in the field of (adaptive) tensor product solution methods for semilinear operator equations by collocation methods, or after transformations between the interpolet and (bi-) orthogonal wavelet bases, by Galerkin methods. Mathematics Subject Classification (2000) 05C05 - 15A69 - 41A05 - 41A63 - 42C40 - 65Y20 - 68Q2