Algorithm for the Rapid Evaluation of Special Function Transforms; Technical rept

摘要

We introduce a fast algorithm for the numerical application to arbitrary vectors of several special function transforms. The algorithm requires O(n log(n)) operations to apply to an arbitrary vector any n n matrix such that the rank of any p q contiguous submatrix is bounded by a constant times pq/n. These rank bounds are proven here for the case of the Fourier- Bessel transform. Numerical experiments demonstrate a much wider applicability. The performance of the algorithm is illustrated via several numerical examples.