A generalized one-dimensional fast multipole method with application to filtering of spherical harmonics

The need to filter functions defined on the sphere arises in a number of applications, such as climate modeling, electromagnetic and acoustic scattering, and several other areas. Recently, it has been observed that the problem of uniform resolution filtering on the sphere can be performed efficiently via the fast multipole method (FMM) in one dimension. In this paper, we introduce a generalization of the FMM that leads to an accelerated version of the filtering process. Instead of multipole expansions, the scheme uses special-purpose bases constructed via the singular value decomposition of appropriately chosen submatrices of the filtering matrix. The algorithm is applicable to a fairly wide class of projection operators; its performance is illustrated with several numerical examples. (C) 1998 Academic Press.