The Cooley-Tukey FFT and Group Theory
David K. Maslen, Daniel N. Rockmore · 2004
In 1965 J. Cooley and J. Tukey published an article detailing an efficient algorithm to compute the Discrete Fourier Transform, necessary for processing the newly available reams of digital time series produced by recently invented analog-to-digital converters. Since then, the CooleyTukey Fast Fourier Transform and its variants has been a staple of digital signal processing. Among the many casts of the algorithm, a natural one is as an efficient algorithm for computing the Fourier expansion of a function on a finite abelian group. In this paper we survey some of our recent work on he “separation of variables” approach to computing a Fourier transform on an arbitrary finite group. This is a natural generalization of the Cooley-Tukey algorithm. In addition we touch on extensions of this idea to compact and noncom pact groups. Pure and Applied Mathematics: Two Sides of a Coin The Bulletin of the AMS for November 1979 had a paper by L. Auslander and R. Tolimieri [3] with the delightful title “Is computing with the Finite Fourier Transform pure or applied mathematics?” This rhetorical question was answered by showing that in fact, the finite Fourier transform, and the family of efficient algorithms used to compute it, the Fast Fourier Transform (FFT), a pillar of the world of digital signal processing, were of interest to both pure and applied mathematicians. Auslander had come of age as an applied mathematician at a time when pure and applied mathematicians still received much of the same training. The ends towards which these skills were then directed became a matter of taste.