Some applications of generalized FFTs

. Generalized FFTs are efficient algorithms for computing a Fourier transform of a function defined on finite group, or a bandlimited function defined on a compact group. The development of such algorithms has been accompanied and motivated by a growing number of both potential and realized applications. This paper will attempt to survey some of these applications. Appendices include some more detailed examples. 1. A brief history The now "classical" Fast Fourier Transform (FFT) has a long and interesting history. Originally discovered by Gauss, and later made famous after being rediscovered by Cooley and Tukey [21], it may be viewed as an algorithm which efficiently computes the discrete Fourier transform or DFT. In between Gauss and Cooley-Tukey others developed special cases of the algorithm, usually motivated by the need to make efficient data analysis of one sort or another. To cite but a few examples, Gauss was interested in efficiently interpolating the orbits of asteroids [43..