An algorithm for the rapid evaluation of special function transforms

Michael O'Neil, Franco Woolfe, Vladimir Rokhlin

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)203-226
Number of pages24
JournalApplied and Computational Harmonic Analysis
Issue number2
StatePublished - Mar 2010


  • Algorithm
  • Fast
  • Fourier-Bessel
  • Matrix
  • Special functions
  • Transform

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'An algorithm for the rapid evaluation of special function transforms'. Together they form a unique fingerprint.

Cite this