Fast evaluation of radial basis functions: Moment-based methods

This paper presents a new method for the fast evaluation of univariate radial basis functions of the form s(x) = Sigma(n=1)(n) d(n)phi(\x - x(n)\) to within accuracy epsilon. The method can be viewed as a generalization of the fast multipole method in which calculations with far field expansions are replaced by calculations involving moments of the data. The method has the advantage of being adaptive to changes in phi. That is, with this method changing to a new phi requires only coding a one- or two-line function for the (slow) evaluation of phi. In contrast, adapting the usual fast multipole method to a new phi involves much mathematical analysis of appropriate series expansions and corresponding translation operators, followed by a substantial amount of work expressing this mathematics in code.