An algorithm for the rapid evaluation of special function transforms

We introduce a new class of fast algorithms for the application to arbitrary vectors of certain special function transforms. The scheme is applicable to a number of transforms, including the Fourier-Bessel transform, the non-equispaced Fourier transform, transforms associated with all classical orthogonal polynomials, etc.; it requires order O (n log (n)) operations to apply an n × n matrix to an arbitrary vector. The performance of the algorithm is illustrated by several numerical examples.