Information | Links | Packages | Subroutines | Utilities
| About this page
Last updated January 8, 2005.
- A Note on FFTs - This article was
written by C.S. Burrus (Rice University). A lengthy list of references
is included.
Return to top
Links to material on FFTs
- Jörg's Useful and
Ugly Pages - This page has links to a great deal of sites
containing information on FFTs. Source code is available in both
FORTRAN and C for many FFT routines.
- DSP Group at Rice - This
page was set up by the Digital Signal Processing Group at Rice
University.
- Netlib - A huge
library of subroutines for computational math
- FFTW - FFTW is a C subroutine
library for performing the DFT in one or more dimensions. At this site,
you'll find the FFTW package, lots of information, benchmarks, and a
large number of links to other resources.
Return to top
- FFTPACK -
A collection of FFT routines written by Paul Swarztrauber.
- FFTW - Fastest Fourier
Transform in the West - A collection of C subroutines.
- GPFA - Routines for the generalized prime
factor fast Fourier transform (written by C. Temperton).
- FFT - Ooura's general purpose 1D FFT
package (N=2**M).
- FFT2D - Ooura's general purpose 2D FFT
package (N=2**M).
- SRFFT - This package contains an
excellent set of split-radix routines for the transformation of real
and complex sequences (N=2**M). The routines employ table lookup of
sines and cosines. A test program is included.
- SFFTB - This package contains a set of
routines for the transformation of real sequences. The routines use
table look-up of sines and cosines and incorporate a bit reversal table
for the in-place bit reversal.
- symFFT - This package is similar to the
set of routines in SRFFT. However, this package also contains a
collection of transforms for real even, real odd, and real quarter wave
even sequences.
Return to top
Split-radix radix-2 transforms
- *SFFTEU - Decimation in frequency, split
radix FFT for complex sequences with N=2**M (written by C.S. Burrus).
- *SFFTFU - Decimation in time, split
radix FFT for complex sequences with N=2**M (written by H.V. Sorensen).
- CTFFTSR - Decimation in frequency,
split radix FFT for complex sequences with N=2**M. Sines and cosines
obtained by table look-up (written by Henrik Sorensen).
- *SFFTCF - Real-to-complex split radix
FFT for sequences of length N=2**M (written by Henrik Sorensen).
- *SFFTCB- Complex-to-real split radix
IFFT for sequences of length N=2**M. (written by Henrik Sorensen).
- RSRFFT - Split radix FFT for real
sequences with N=2**M. Sines and cosines are computed recursively.
- IRSRFFT - Inverse routine for RSRFFT.
Sines and cosines are computed recursively.
Cooley-Tukey radix-2 transforms
- CFFT - Cooley-Tukey radix-2 decimation in
frequency FFT for complex sequences with N=2**M. Sines and cosines
stored in tables.
- *CFFT - Same routine as above, except
without table look-up of sines and cosines. Also in
C++.
- *RFFT - Cooley-Tukey radix-2 decimation in
time FFT for real sequences with N=2**M (written by Henrik Sorensen).
- FFT - Complex FFT from NASA LaRC COMPUTER
MANUAL.
- FFT - Stockham Auto-sort FFT. (I haven't
tested these routines.)
- FFT - Yet another FFT. (I haven't tested
this one.)
Radix 4 transforms
- FASTF - Radix-4 FFT for complex
sequences.
- FASTF - Radix-4 FFT for complex
sequences. (This is very much like the one above.)
Generalized Prime Factor FFT
- GPFA - Routines for the generalized prime
factor FFT (written by C. Temperton).
Mixed radix transforms
- FFT - Complex FFT from the NAPACK library.
- FFT - Complex FFT written by R.C.
Singleton.
Discrete Cosine Transforms
- FCT - Fast discrete cosine transform
written by B. Sherlock and D. Monro.
Fast Hartley Transforms
- FHTFR - Fast Hartley Transform. I don't
have a reference for this, except what's included with the code.
Return to top
Return to top
This information is provided by S. Kifowit. Please feel
free to send me any comments or suggestions. Click here to visit my
homepage.
The fast Fourier transform is an extremely important
computational tool. In my research, I use FFTs for fast
polynomial multiplication and for inversion of circulant systems.
When it initially became clear to me that I had a need for FFT
routines, I was immediately referred to FFTPACK,
written by Paul Swarztrauber. As my needs became more
specialized, finding routines became more difficult. With this in
mind, I attempted to develop a site that contains information
and routines that are helpful to those in a situation like mine.
If you have any user-friendly FORTRAN subroutines that you think
should be included on this page, please let me know. Unless otherwise
indicated, I have tested (and used) all of the FORTRAN
routines included on this page. Nonetheless, I cannot guarantee
that they are
free of errors.
Please note that I have desperately tried to give credit where
credit is due. Whenever I have any information about the author
of a routine, I include it along with any known references.
* The routines above that are marked with an asterick (*) are very
simple to use and are appropriate "starting" routines
for those unfamiliar with FFTs.
Return to top
