The term fast Fourier transform (FFT) refers to an efficient
implementation of the discrete Fourier transform (DFT) for highly
compositeA.1 transform
lengths
. When computing the DFT as a set of
inner products of
length
each, the computational complexity is
. When
is an integer power of 2, a Cooley-Tukey FFT algorithm delivers
complexity
, where
denotes the log-base-2 of
, and
means ``on the order of
''.
Such FFT algorithms were evidently first used by Gauss in 1805
[31] and rediscovered in the 1960s by Cooley and Tukey
[17].
In this appendix, a brief introduction is given for various FFT algorithms. A tutorial review (1990) is given in [23]. Additionally, there are some excellent FFT ``home pages'':
Pointers to FFT software are given in §A.7.