15.8 References and Further Reading

A good starting point for learning more about the FFT is the review article Fast Fourier Transforms: A Tutorial Review and A State of the Art by Duhamel and Vetterli,

• P. Duhamel and M. Vetterli. Fast fourier transforms: A tutorial review and a state of the art. Signal Processing, 19:259–299, 1990.

To find out about the algorithms used in the GSL routines you may want to consult the document GSL FFT Algorithms (it is included in GSL, as ‘doc/fftalgorithms.tex’). This has general information on FFTs and explicit derivations of the implementation for each routine. There are also references to the relevant literature. For convenience some of the more important references are reproduced below.

There are several introductory books on the FFT with example programs, such as The Fast Fourier Transform by Brigham and DFT/FFT and Convolution Algorithms by Burrus and Parks,

• E. Oran Brigham. The Fast Fourier Transform. Prentice Hall, 1974.
• C. S. Burrus and T. W. Parks. DFT/FFT and Convolution Algorithms. Wiley, 1984.

Both these introductory books cover the radix-2 FFT in some detail. The mixed-radix algorithm at the heart of the FFTPACK routines is reviewed in Clive Temperton's paper,

• Clive Temperton. Self-sorting mixed-radix fast fourier transforms. Journal of Computational Physics, 52(1):1–23, 1983.

The derivation of FFTs for real-valued data is explained in the following two articles,

• Henrik V. Sorenson, Douglas L. Jones, Michael T. Heideman, and C. Sidney Burrus. Real-valued fast fourier transform algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-35(6):849–863, 1987.
• Clive Temperton. Fast mixed-radix real fourier transforms. Journal of Computational Physics, 52:340–350, 1983.

In 1979 the IEEE published a compendium of carefully-reviewed Fortran FFT programs in Programs for Digital Signal Processing. It is a useful reference for implementations of many different FFT algorithms,

• Digital Signal Processing Committee and IEEE Acoustics, Speech, and Signal Processing Committee, editors. Programs for Digital Signal Processing. IEEE Press, 1979.

For large-scale FFT work we recommend the use of the dedicated FFTW library by Frigo and Johnson. The FFTW library is self-optimizing—it automatically tunes itself for each hardware platform in order to achieve maximum performance. It is available under the GNU GPL.

• FFTW Website, http://www.fftw.org/

The source code for FFTPACK is available from Netlib,

• FFTPACK, http://www.netlib.org/fftpack/