Introduction

Another good place to go when you have signal-processing and/or FFT-related questions is Usenet, and in particular the comp.dsp (digital signal processing), sci.math.num-analysis (numerical analysis and scientific computation), or sci.image.processing (image processing) groups.

Let us know if you think there are other links that we should include. Last updated: 23 April 2007.

FFT Source Code

• The FFTW Home Page: A fast C library for performing the FFT in one or more dimensions, including parallel and real-data transforms. Of course, we have to include ourselves in this list!
• FFT Sources: This is the list of all the codes that we included in benchFFT, along with links to where they may be downloaded. It is one of the more complete FFT-software listings available.
• Jörg's "Ugly" Page: Jörg Arndt has gathered a menagerie of FFT links and source code, including much of the software that we used in our benchmark. (Somewhat chaotically organized.)
• An FFT Page maintained by Steve Kifowit, focusing primarily on Fortran code.
• D. J. Bernstein has written an optimized C FFT for the Pentium and UltraSPARC. (Its output is permuted and it is limited to N <= 8192, but this doesn't prevent it from being used e.g. for convolutions. It includes convolution routines for real and complex data.) (See also pfftw.)
• Some programs for related problems:
  • NFFT is a free library for non-equispaced discrete Fourier transforms (and also DCTs/DSTs), based on FFTW. NFFT also provides an "FFT" on a unit sphere (decomposition into spherical harmonics).
  • ccSHT is another free library implementing spherical harmonic transforms (using a different algorithm), based again on FFTW.

Benchmarks

• Our benchFFT package compares performance of many FFT implementations in both C and Fortran (and we have posted speed and accuracy results from a number of machines).
• Greg Allen has published benchmarks of Altivec FFTs.
• The FFT Processor Information Page by Bevan Baas compares a lot of special-purpose FFT hardware.

Explanatory Material

• There is a survey and history of FFT algorithms and related information in the free Wikipedia collaborative encyclopedia.
• Numerical Recipes, which is readable on-line (with a special plugin, unfortunately), has a decent introduction to Fourier transforms, DFTs, and FFTs (albeit somewhat dated).
• For a good description of the FFT literature c. 1997 (with many references), see C. S. Burrus's "Notes on the FFT" (our mirror of the now-missing original).
• The Scientist's and Engineer's Guide to Digital Signal Processing is an entire DSP book free online by Steven W. Smith.
• Another book online: Mathematics of the Discrete Fourier Transform (DFT)—With Music and Audio Applications, by Julius O. Smith III.
• The Picture Book of Fourier Transforms by Kevin Cowtan gives an interesting graphical tutorial on the interpretation of 2D FFT output, with a special emphasis on crystallography. There is also a tutorial on Fourier transforms, the convolution theorem, and other material.
• An"intuitive explanation of Fourier theory" by Steven Lehar.
• DFT and FFT Introduction by Paul Bourke, describing the discrete Fourier transform in one and two dimensions in terms of the continuous transform, with examples of the transforms of various functions. Also has introductions to digital filters, image filtering, and other related topics.
• A chapter on the history of Fourier's theorem, from the charming book Trigonometric Delights (readable online) by Eli Maor.
• A biography of Jean Fourier can be found at the excellent MacTutor History of Mathematics Archive; there is also another biography of Jean Fourier on Wikipedia.
• The FFT Demystified is a site by Adrian Hey covering many introductory and not-so-introductory aspects of FFT algorithms.
• The book Numerical Computing with MATLAB online has a tutorial on Fourier analysis based on Matlab's fft function (which uses FFTW).
• A mostly non-mathematical introduction to Fourier transforms at the site of a DSP company with the (hopefully non-descriptive) name of Bores.
• DSP Dimension, by Stephan M. Bernsee, contains tutorials and other links for Fourier analysis and DSP, focusing on audio processing.
• dspGuru contains various tutorials, FAQs, and other information related to digital signal processing (and FFTs).
• DSPRelated.com is another site collecting DSP links and discussion groups.
• A "graphical interpretation" of the DFT and FFT, by Steve Mann.
• Scanned copies of the original Cooley & Tukey FFT paper.
• Integrate your function times a complex exponential... Sing along with "Fourier's Song."
• The FFT Laboratory site has a neat Java applet for experimenting with the DFT.

Miscellaneous FFT-related Links

• The AURORA project explores a variety of scientific-computing topics, including FFTs that use SIMD instructions such as Altivec and SSE. Among other things, they have developed variants of FFTW for the AMD 3DNow! and the Intel SSE/SSE2 instruction sets (see also FFTW 3.0).
• SPIRAL is a project to express FFTs and related algorithms (e.g. Walsh-Hadamard transforms) in terms of a generalized Tensor Product Language (TPL), from which source code, matrix representations, etcetera, can be generated.
• There is a Parallel FFT group at the Univ. of Houston.
• For something a bit farther out, look at Alan Edelman's new algorithm to compute the DFT of very large data sets on parallel architectures.
• gmeteor is a flexible program for generating optimal FIR filters with an arbitrary frequency response.
• Harminv is a program/library that decomposes a time series as a sum of a few decaying sinusoids, equivalent to (but more robust than) extracting peaks from an FFT spectrum,

Other Sites of Interest

• Netlib is a famous repository of free numerical software.
• Cilk is an awesome way to write parallel programs on shared-memory machines. For message passing, MPI isn't bad. The Beowulf Project is one good way to build your own parallel machine.
• NA-Net has a useful weekly digest on topics related to numerical analysis.
• PhiPAC and ATLAS are projects applying auto-optimization and code-generation techniques to produce fast BLAS matrix routines (somewhat similar in spirit to FFTW). See also the BeBOP group at Berkeley.

Translations of this page

• Ukrainian translation by Max Harchenko (http://iphostmonitor.com).