Multipole expansions and pseudospectral cardinal functions: A new generalization of the fast fourier transform

Abstract

The polynomial or trigonometric interpolant of an arbitrary function f(x) may be represented as a "cardinal function" series whose coefficients are the values of f(x) at the interpolation points. We show that the cardinal series is identical to the sum of the forces due to a set of N point charges (with appropriate force laws). It follows that the cardinal series can be summed via the fast multipole method (FMM) in O(N log2 N) operations, which is much cheaper than the O(N2) cost of direct summation. The FM M is slower than the fast Fourier transform (FFT), so the latter should always be used where applicable. However, the multipole expansion succeeds where the FFT fails. In particular, the FMM can be used to evaluate Fourier and Chebyshev series on an irregular grid as is needed when adaptively regridding in a time integration. Also, the multipole expansion can be applied to basis sets for which the FFT is inapplicable even on the canonical grid including Legendre polynomials, Hermite and Laguerre functions, spherical harmonics, and slnc functions.