Send questions and comments to Dan Rockmore rockmore@cs.dartmouth.edu or Peter Kostelec geelong@cs.dartmouth.edu

J. W. Cooley, "The re-discovery of the fast Fourier transform algorithm", Mikrochimica Acta III (1987), 33--45.

J. W. Cooley, "How the FFT gained acceptance", Proceedings of the ACM conference on the history of scientific and numeric computation, Princeton, NJ May 13--15, 1987, 133--140.

M. T. Heideman, D. H. Johnson, and C. S. Burrus, Gauss and the history of the fast Fourier transform, Archive for History of Exact Sciences 34(3) (1985), 265--277.

There are many ways to approach the FFT. The point of view of the work collected here is a group theoretic one. In this setting the FFT is a family of algorithms for the efficient expansion of a function defined on a finite or compact group in terms of a set of irreducible matrix coefficients for the group. For the circle these are precisely the exponentials or sampled exponentials in the case of the discrete circle. Consideration of noncommutative groups gives rise to the many families of special functions, the most familiar of which are probably the Legendre functions and other Gegenbauer polynomials and systems of orthogonal polynomials.

We assume that initially, the function is "given" as a finite set of sample values on the group in question - in the classical setting the group is the circle (discrete or continuous) and is usually identified with time or space - and the forward Fourier transform consists in the computation of the Fourier coefficients for the expansion of the function in terms of a predetermined set of irreducible matrix coefficients on the group. Of course the assumption is that these are finite expansions, and this effectively defines the general notion of "bandlimited" as a function with finite expansion in terms of irreducible matrix coefficients.

For a more thorough introduction to these ideas see the survey papers

Motivated by a variety of applications to data analysis and combinatorics a loosely knit group of us have been working on different aspects of the development and application of these algorithms. Here are some of us:

- Richard Foote (UVM)
- Dennis Healy (Dartmouth, DARPA)
- Albin Jones (Dartmouth)
- Peter Kostelec (Dartmouth)
- John Lafferty (CMU)
- David Maslen (Utrecht)
- Gagan Mirchandani (UVM)
- Tim Olson (UFla)
- Michael Ringenburg (Dartmouth)
- Dan Rockmore (Dartmouth)
- Mark Taylor (NCAR)
- Doug Warner (Dartmouth)

For related work also see

At present (June 1999) our work mainly falls into two categories:

- (1) Fast spherical harmonic expansions: a brief description may be found here; preprint and software available here.
- (2) FFTs for finite groups, especially the symmetric groups and their wreath products and the special linear groups over finite fields. Links to relevant publications may be found here; links to software may be found here.

- The symmetric group
- Spherical harmonics
- SL_2(F)
- Block designs
- (Z/nZ)^k: Short length (n = 2, 3, 4), high dimensional FFTs, gzipped or not gzipped
- The Rotation Group, SO(3)

There have been visitors since March 20, 1998. This work has been partially funded by an NSF Presidential Faculty Fellowship, NSF DMS-9553134.