Go back to the FFTW home page.
There are many other places that you can go on the Web to learn more
about Fourier Transforms in general and FFTs in particular. Since searching for "FFT" on Alta
Vista will yield far too many links, most of them useless
(although Google has
improved matters somewhat), we decided to list a few of the better
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 following are places where you can download source code for FFTs.
(There are so many FFT implementations available that we mostly link to
sites that are themselves collections of code or links.)
- 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!
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
- 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.
Sites to help you decide which FFT implementation to use.
Tutorials and introductions to Fourier transforms and FFTs, in no
- There is a survey and
history of FFT algorithms and related information in the free Wikipedia collaborative
- Numerical Recipes, which is readable on-line (with a special plugin,
unfortunately), has a decent introduction to Fourier
transforms, DFTs, and FFTs (albeit somewhat
- 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
filtering, and other related
- 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, placed online by Charles Chiu
- Integrate your function times a complex exponential... Sing along with "Fourier's
- The FFT
Laboratory site has a neat Java applet for experimenting with
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
- 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
- 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.
Go back to the FFTW home page.