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(nlog(n)) operations to apply an n×n matrix to an arbitrary vector. The performance of the algorithm is illustrated by several numerical examples.