8

The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases such as Hermite, Legendre, Chebyshev,...? I have a special interest in Zernike polynomials as well. If so, how? If not, what is special about the sin/cos that separates it from the other cases?

Also asked previously on: https://math.stackexchange.com/questions/647613/fast-fourier-transform-for-non-trigoniometric-bases/1730645#1730645 not having quite a satisfying answer yet.

Also, in a related question here on MO (here), I see pointing to this document on why the FFT would be fast. How could I use this principle on general orthogonal bases?

Community
  • 1
Lense
  • 81
  • 1
    Did you have a look at stuff like: https://www.brown.edu/research/projects/scientific-computing/sites/brown.edu.research.projects.scientific-computing/files/uploads/The%20application%20of%20the%20Fast%20Fourier%20Transform%20to%20Jacobi%20polynomial%20expansions.pdf – Suvrit Apr 11 '16 at 21:57

1 Answers1

2

Related questions have been considered in some depth by Dan Rockmore and collaborators. For more, check out Rockmore's web page.

Igor Rivin
  • 95,560