Benchmarked FFT Implementations

The following is the list of FFT codes (both free and non-free) that we included in our speed and accuracy benchmarks, along with bibliographic references and a few other notes to make it easier to compare the data in our results graphs.

(Not every FFT is benchmarked on every machine, either because the code was not installed/available on that machine or because some glitch prevented it from compiling.)

• AMD Core Math Library (ACML)

  • Benchmark label: acml
  • Note: transform is scaled by sqrt(n)
  • Note: using the runtime planner (MODE=100)

• arprec

  • URL: http://crd.lbl.gov/~dhbailey/mpdist/ (was valid on Thu Aug 21 17:07:36 EDT 2003)
  • Authors: David H. Bailey, Yozo Hida, Xiaoye S. Li, Brandon Thompson
  • Email address: dhbailey atta lbl dotta gov
  • Year: 2002
  • Version: 2002-08-27
  • Language: C++
  • References: D. H. Bailey, J. of Supercomputing, p. 23-35 (March 1990)
  • Note: Part of the ARPREC arbitrary-precision arithmetic library.
  • Note: Employs two-pass 4-step and Stockham FFT algorithms.
  • Note: Based on code in DHB's MPFUN package
  • Note: A new version was released on 2003-07-14, but has not made it into our benchmark yet. Sorry about that.

• bloodworth

  • Author: Carey E. Bloodworth
  • Email address: cbloodworth atta juno dotta com
  • Year: 1998
  • Language: C
  • Note: Received in personal communication from the author.
  • Note: Slightly modified for benchFFT 2.0 (some subroutine names changed, and code slightly altered to work with both single and double precision...original code was double precision, I think).
  • Benchmarked variants:
    • bloodworth
      • Note: The backwards transform is scaled.
    • bloodworth-fht
      • Note: Uses a Fast Hartley Transform (FHT) algorithm.

• burrus-sffteu

  • URL: http://ourworld.compuserve.com/homepages/steve_kifowit/sffteu.txt (was valid on Mon Jul 16 00:03:31 EDT 2001)
  • Author: C. S. Burrus
  • Year: 1984
  • Language: Fortran 77
  • References: Electronics Letters, January 5, 1984
  • Note: Complex data are stored in separate real/imag arrays.

• Compaq/Digital Extended Math Library (CXML/DXML)

  • Benchmark label: cxml
  • Note: 3d transform
  • Note: We benchmark using the complex array format.

• cross

  • URL: http://www.intersrv.com/~dcross/fft.html (was valid on Mon Sep 2 21:54:04 EDT 2002)
  • Author: Don Cross
  • Email address: dcross atta intersrv dotta com
  • Year: 1998
  • Language: C
  • Note: Complex data are stored in separate real/imag arrays.
  • Note: The forward transform is scaled.

• cwplib

  • URL: http://www.cwp.mines.edu/cwpcodes/ (was valid on Tue Jan 24 18:54:17 EST 2006)
  • Author: Dave Hale
  • Year: 1998
  • Version: Release 39
  • Language: C
  • Note: Prime-factor algorithm.
  • Note: Revised by Baoniu Han to handle double precision. 12/14/98
  • Note: Benchmark uses the files pfafft.c, dpfafft.c, and cwp.h, which are included as a part of the CWP/SU Seismic Un*x package.

• dfftpack

  • URL: ftp://ftp.netlib.org:/fftpack/dp.tgz (was valid on Thu Jul 12 20:26:24 EDT 2001)
  • Author: Paul N. Swarztrauber and Hugh C. Pumphrey
  • Year: 1985
  • Version: 1.0
  • Language: Fortran 77
  • References: P. N. Swarztrauber, Vectorizing the FFTs, Parallel Computations, p. 51-83 (1982).

• emayer

  • Author: Ernst W. Mayer
  • Email address: ewmayer atta aol dotta com
  • Year: 1997
  • Language: Fortran 90
  • Note: A later (radix-16) version of this code was published in the Mersenne Prime Freeware collection; the later version merges forward and backwards transforms and so is more difficult to benchmark.
  • Note: The original URL for this code is now defunct.

• esrfft

  • URL: http://www.ffte.jp/ (was valid on Fri Jan 3 16:11:54 EST 2003)
  • Author: Daisuke Takahashi
  • Email address: daisuke atta is dotta tsukuba dotta ac dotta jp
  • Year: 2002
  • Language: Fortran 77
  • References: D. Takahashi, An extended split-radix FFT algorithm, IEEE Signal Processing Lett. 8, pp. 145-147, May 2001.
  • Note: Complex data are stored in separate real/imag arrays.
  • Note: The backward transform is scaled, and also has an additional pre-processing pass to flip the sign of the input imaginary part. Since the code accepts the real/imag parts as separate arrays, we instead swap the arguments to avoid this overhead.

• essl

  • URL: http://www.rs6000.ibm.com/software/Apps/essl.html (was valid on Tue Aug 14 15:07:49 EDT 2001)
  • Author: IBM
  • Note: ESSL is the IBM Engineering and Scientific Subroutine Library.

• ffmpeg

  • URL: http://ffmpeg.sourceforge.net/ (was valid on Sun Sep 4 21:02:50 EDT 2005)
  • Author: Fabrice Bellard
  • Email address: fabrice atta bellard dotta org
  • Year: 2002
  • Version: Lavc49.0.2
  • Language: C
  • Note: Complex-data FFT routines from libavcodec, with whatever compilation flags were used for the libavcodec installed on the system.
  • Note: Benchmarked ff_fft_permute + ff_fft_calc pair of routines, so that we are benchmarking the normal-order FFT.

• ffte

  • URL: http://www.ffte.jp/ (was valid on Tue Apr 29 07:48:19 EDT 2003)
  • Author: Daisuke Takahashi
  • Email address: daisuke atta is dotta tsukuba dotta ac dotta jp
  • Year: 2004
  • Version: 4.0
  • Language: Fortran 77
  • References: Daisuke Takahashi, A Parallel 3-D FFT Algorithm on Clusters of Vector SMPs, Proc. 5th International Workshop on Applied Parallel Computing (PARA 2000), Lecture Notes in Computer Science, No. 1947, Springer-Verlag, pp. 316-323 (2001). Daisuke Takahashi, A Blocking Algorithm for FFT on Cache-Based Processors, Proc. 9th International Conference on High Performance Computing and Networking Europe (HPCN Europe 2001), Lecture Notes in Computer Science, No. 2110, Springer-Verlag, pp. 551-554 (2001). Daisuke Takahashi, A Blocking Algorithm for Parallel 1-D FFT on Shared-Memory Parallel Computers, Proc. 6th International Conference on Applied Parallel Computing (PARA 2002), Lecture Notes in Computer Science, Springer-Verlag, in press.
  • Note: The backwards transform is scaled.
  • Note: Benchmark uses default blocking parameter NBLK=16, padding parameter NP=8, and cache parameter L2SIZE=1048576
  • Benchmarked variants:
    • ffte
    • ffte-v
      • Note: vector-machine version

• fftpack

  • URL: ftp://ftp.netlib.org:/fftpack (was valid on Thu Jul 12 20:26:24 EDT 2001)
  • Author: Paul N. Swarztrauber
  • Year: 1985
  • Version: 4
  • Language: Fortran 77
  • References: P. N. Swarztrauber, Vectorizing the FFTs, Parallel Computations, p. 51-83 (1982).

• FFTReal

  • URL: http://ldesoras.free.fr/prod.html (was valid on Sat Feb 12 18:41:20 EST 2005)
  • Benchmark label: fftreal
  • Author: Laurent de Soras
  • Email address: ldesoras atta club-internet dotta fr
  • Year: 2001
  • Version: 1.03
  • Language: C++
  • Note: Code is in single precision, but double precision version is created as documented by the author, by changing the flt_t typedef in the FFTReal.h header file

• FFTs for RISC 2.0

  • URL: http://hyperarchive.lcs.mit.edu/HyperArchive/Archive/dev/src/ffts-for-risc-2-c.hqx (was valid on Sun Jul 15 21:28:59 EDT 2001)
  • Benchmark label: green
  • Author: John Green
  • Email address: green_jt atta vsdec dotta npt dotta nuwc dotta navy dotta mil
  • Year: 1998
  • Language: C
  • Note: The backward transform is scaled
  • Note: Code is in single precision, but double precision version is created as documented by the author: ``for double precision just use a global search and replace to change float to double in all source files.''

• FFTW 2

  • URL: http://www.fftw.org (was valid on Fri Mar 28 18:46:22 EST 2003)
  • Authors: Matteo Frigo, Steven G. Johnson
  • Email address: fftw atta fftw dotta org
  • Year: 2003
  • Version: FFTW V2.1.3 ($Id: executor.c,v 1.66 1999/10/26 21:41:29 stevenj Exp $)
  • Languages: C, Objective Caml
  • References: M. Frigo and S. G. Johnson, FFTW: An adaptive software architecture for the FFT, Proc. ICASSP 3, 1381-1384 (1998)
  • Benchmarked variants:
    • fftw2-estimate
      • Note: Using 1-dimensional interface, FFTW_ESTIMATE flag
    • fftw2-measure
      • Note: Using 1-dimensional interface, FFTW_MEASURE flag
    • fftw2-nd-estimate
      • Note: Using N-dimensional interface, FFTW_ESTIMATE flag
    • fftw2-nd-measure
      • Note: Using N-dimensional interface, FFTW_MEASURE flag

• FFTW 3.1

  • URL: http://www.fftw.org (was valid on Fri Mar 28 18:46:22 EST 2003)
  • Authors: Matteo Frigo, Steven G. Johnson
  • Email address: fftw atta fftw dotta org
  • Year: 2006
  • Languages: C, Objective Caml
  • References: M. Frigo and S. G. Johnson, FFTW: An adaptive software architecture for the FFT, Proc. ICASSP 3, 1381-1384 (1998)
  • Benchmarked variants:
    • fftw3
      • Note: Using unpacked complex format for real transforms.
    • fftw3-r2r
      • Note: Using halfcomplex transform interface (R2HC/HC2R kinds).

• FXT

  • URL: http://www.jjj.de/fxt/ (was valid on Thu Jan 5 16:46:39 EST 2006)
  • Author: Jörg Arndt
  • Email address: arndt atta jjj dotta de
  • Year: 2005
  • Version: 20-November-2005
  • Language: C++
  • Note: For GNU g++, we use whatever CXXFLAGS are selected by fxt's makefile
  • Benchmarked variants:
    • fxt-cdif4
      • Note: Radix-4 DIF algorithm, interleaved real/imag format
    • fxt-cdit4
      • Note: Radix-4 DIT algorithm, interleaved real/imag format
    • fxt-cfht
      • Note: FFT by FHT algorithm, interleaved real/imag format.
    • fxt-cmatrixfft
      • Note: Four-step algorithm, uses FHT for sub-FFTs, interleaved real/imag format.
    • fxt-csplit
      • Note: Split-radix algorithm, interleaved real/imag format.
    • fxt-depth-first-dif2
      • Note: Radix-2 DIF with swapped loop order, interleaved real/imag format.
    • fxt-depth-first-dit2
      • Note: Radix-2 DIT with swapped loop order, interleaved real/imag format.
    • fxt-dif2
      • Note: Radix-2 DIF, interleaved real/imag format.
    • fxt-dif4
      • Note: Radix-4 DIF algorithm, split real/imag format
      • Note: Complex data are stored in separate real/imag arrays.
    • fxt-dit2
      • Note: Radix-2 DIT, interleaved real/imag format.
    • fxt-dit4
      • Note: Radix-4 DIT algorithm, split real/imag format
      • Note: Complex data are stored in separate real/imag arrays.
    • fxt-fht
      • Note: FFT by FHT algorithm, split real/imag format
      • Note: Complex data are stored in separate real/imag arrays.
    • fxt-fht-real
      • Note: FFT by FHT algorithm.
    • fxt-gray
      • Note: Radix-2 'Gray-code' algorithm, interleaved real/imag format.
    • fxt-matrixfft
      • Note: Four-step algorithm, uses FHT for sub-FFTs, split real/imag format.
      • Note: Complex data are stored in separate real/imag arrays.
    • fxt-ndim
      • Note: Uses FHT for 1d FFTs.
      • Note: Complex data are stored in separate real/imag arrays.
    • fxt-recursive-dif2
      • Note: Recursive radix-2 DIF, interleaved real/imag format.
    • fxt-recursive-dit2
      • Note: Recursive radix-2 DIT, interleaved real/imag format.
    • fxt-split
      • Note: Split-radix algorithm, split real/imag format.
      • Note: Complex data are stored in separate real/imag arrays.
    • fxt-split-real
      • Note: FFT by real-data split-radix algorithm. Original Fortran code by Sorensen; published in H.V. Sorensen et al., Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech Sig. Proc. 35, 849-863 (1987). Adapted to C by Bill Simpson, 1995. Further optimizations by Joerg Arndt.
    • fxt-twodim
      • Note: Uses FHT for 1d FFTs.
      • Note: Complex data are stored in separate real/imag arrays.
    • fxt-wrap-real
      • Note: Real-data FFT by wrapping half-size complex FFT (via FHT).

• glassman

  • URL: http://www.jjj.de/fft/glassman-fft.f (was valid on Sun Nov 17 22:40:20 EST 2002)
  • Language: Fortran 77
  • References: W. E. Ferguson, Jr., A simple derivation of Glassman general-n fast Fourier transform, Comput. and Math. with Appls. 8 (6), 401-411 (1982). Also in Report AD-A083 811, NTIS, Dec. 1979. J. A. Glassman, A generalization of the fast Fourier transform, IEEE Trans. on Computers 19 (2), 105-116 (1970).
  • Note: The backward transform is scaled.
  • Note: Uses an unstable trigonometric iteration.

• GNU Scientific Library (GSL)

  • URL: http://sources.redhat.com/gsl (was valid on Thu Jul 26 07:48:45 EDT 2001)
  • Author: Brian Gough
  • Year: 2002
  • Version: 1.7
  • Language: C
  • Benchmarked variants:
    • gsl-mixed-radix
    • gsl-radix2
    • gsl-radix2-dif
    • gsl-radix2-dit

• goedecker

  • URL: http://www.abinit.org/ (was valid on Thu May 22 00:37:07 EDT 2003)
  • Author: Stefan Goedecker
  • Year: 1993
  • Note: This routine was downloaded as part of the ABINIT-3.1.3 software.
  • Note: Slightly modified for the benchmark. See sgfft.tar.gz for the original code.
  • Note: The fftcache parameter is set to 16KB. This may be wrong on your system.

• gpfa

  • Author: Clive Temperton
  • Year: 1992 (?)
  • Language: Fortran 77
  • Benchmarked variants:
    • gpfa
      • URL: http://risc2.numis.nwu.edu/ftp/pub/transforms/gpfa.tar.gz (was valid on Sat Aug 31 16:37:44 EDT 2002)
      • References: C. Temperton, A Generalized Prime Factor FFT Algorithm for Any N = (2**P)(3**Q)(5**R), SIAM J. Sci. Stat. Comp. 13 (3),p. 676-686 (May 1992).
    • gpfa-3d
      • References: C. Temperton, A Generalized Prime Factor Fft Algorithm For Any N = (2**P)(3**Q)(5**R), SIAM J. Sci. Stat. Comp. 13 (3),p. 676-686 (May 1992).

• harm

  • URL: http://risc2.numis.nwu.edu/ftp/pub/transforms/ (was valid on Sat Aug 31 16:37:44 EDT 2002)
  • Language: Fortran 77
  • References: May be related to radix-4 PK HARM subroutine mentioned in J. W. Cooley and P. A. W. Lewis and P. D. Welch, The Fast Fourier Transform Algorithm and Its Applications (IBM Research, 1967).
  • Note: The backward transform is scaled

• HP Mathematical Software Library (mlib, a.k.a. veclib)

  • URL: http://h21007.www2.hp.com/dspp/tech/tech_TechSoftwareDetailPage_IDX/1,1703,1204,00.html (was valid on Thu Feb 5 23:41:33 EST 2004)
  • Benchmark label: hp-mlib
  • Note: We benchmark the complex (interleaved real/imag) format for complex transforms.
  • Note: We benchmark the non-redundant format for real data (real input array, half of complex output array).
  • Note: We benchmark the unscaled inverse in 1d.

• IMSL (International Mathematical and Statistical Library)

  • URL: http://www.vni.com/products/imsl/ (was valid on Mon Jan 14 21:15:19 EST 2002)
  • Benchmark label: imsl
  • Author: Visual Numerics, Inc.
  • Note: IMSL's FFT routines are based on FFTPACK.
  • Note: Benchmark uses the Fortran 77 interface.

• Intel Integrated Performance Primitives, Signal Processing (IPPS)

  • Benchmark label: intel-ipps
  • Version: v3.0 gold 3.0.18.57
  • Note: Using ``Perm'' format for real transforms.

• JMFFT

  • URL: http://www.idris.fr/data/publications/JMFFT/ (was valid on Sat Aug 31 02:45:22 EDT 2002)
  • Benchmark label: jmfftc
  • Author: Jean-Marie Teuler
  • Email addresses: teuler atta virgo dotta infn dotta it, Jalel dotta Chergui atta idris dotta fr
  • Year: 2000
  • Version: 1.0
  • Language: C
  • Note: Designed to emulate the FFTs in Cray's SCILIB.
  • Note: A Fortran-90 version is also available.

• kissfft

  • URL: http://sourceforge.net/projects/kissfft/
  • Author: Mark Borgerding
  • Year: 2005
  • Version: 1.2.4
  • Language: C

• krukar

  • URL: http://risc2.numis.nwu.edu/ftp/pub/transforms/ffts_in_C.tar.gz (was valid on Sat Aug 31 16:36:36 EDT 2002)
  • Author: Richard H. Krukar
  • Email address: krukar atta ectopia dotta com
  • Year: 1990
  • Language: C
  • Note: The backward transform is scaled

• mfft

  • URL: http://risc2.numis.nwu.edu/ftp/pub/transforms/mfft.tar.gz (was valid on Sat Aug 31 16:35:13 EDT 2002)
  • Author: A. Nobile and V. Roberto
  • Year: 1987
  • Language: Fortran 77
  • References: A. Nobile and V. Roberto, MFFT: A package for two- and three-dimensional vectorized discrete Fourier transforms, Computer Physics Communications 42, p. 233 (1986).

• mixfft

  • URL: http://hjem.get2net.dk/jjn/fft.htm (was valid on Mon Feb 10 01:19:57 EST 2003)
  • Author: Jens Joergen Nielsen
  • Email address: jjn atta get2net dotta dk
  • Year: 2000
  • Version: 0.5
  • Language: C
  • Note: Complex data are stored in separate real/imag arrays.

• monnier

  • URL: http://www.igd.u-bordeaux.fr/~monnier/fft.html (was valid on August 1998 (?))
  • Author: Yves Monnier
  • Year: 1995
  • Language: C
  • Note: Slightly modified for original benchfft; original version has disappeared from the Web.
  • Note: Although a pre-computed trigonometric table is used, the phase angle in the table is calculated by repeated addition, resulting in poor accuracy even for moderate transform sizes.

• morris82

  • Author: L. Robert Morris
  • Year: 1982
  • Language: Fortran 77
  • Note: Received in personal communication from the author, Apr 21 2003
  • Note: Complex data are stored in separate real/imag arrays.
  • Note: Published in: Digital Signal Processing Software, DSPS Inc, 1983

• mpfun77

  • URL: http://www.nersc.gov/~dhbailey/mpdist/mpdist.html (was valid on Mon Sep 2 00:48:38 EDT 2002)
  • Author: David H. Bailey
  • Email address: dhbailey atta lbl dotta gov
  • Year: 1988
  • Language: Fortran 77
  • References: D. H. Bailey, Intl. J. of Supercomp. Appl., p. 82-87 (Spring 1988).
  • Note: Complex data are stored in separate real/imag arrays.
  • Note: Part of the MPFUN multi-precision arithmetic library.
  • Note: Employs 4-step and Stockham FFT algorithms.
  • Note: Patched by S. G. Johnson to allow arrays to be allocated from C caller.

• mpfun90

  • URL: http://www.nersc.gov/~dhbailey/mpdist/mpdist.html (was valid on Mon Sep 2 00:48:38 EDT 2002)
  • Author: David H. Bailey
  • Email address: dhbailey atta lbl dotta gov
  • Year: 2001
  • Language: Fortran 90
  • References: D. H. Bailey, J. of Supercomputing, p. 23-35 (March 1990)
  • Note: Part of the MPFUN90 multi-precision arithmetic library.
  • Note: Employs two-pass 4-step and Stockham FFT algorithms.

• NAG Fortran Library

  • URL: http://www.nag.com/ (was valid on Wed Aug 15 13:43:43 EDT 2001)
  • Author: Numerical Algorithms Group
  • Note: both forward and backward transforms are scaled
  • Benchmarked variants:
    • nag-cmplx
      • Note: Uses c06pcf and friends: complex data type (interleaved real/imaginary parts), extra workspace supplied.
    • nag-inplace
      • Note: Uses c06ecf and friends (in-place, no workspace).
      • Note: Complex data are stored in separate real/imag arrays.
      • Note: forwards and backwards real transforms have the same sign
    • nag-multiple
      • Note: Uses functions c06frf and friends: interface for multiple simultaneous transforms (not used), precomputed trig. tables, and extra workspace supplied.
      • Note: Complex data are stored in separate real/imag arrays.
      • Note: forwards and backwards real transforms have the same sign
    • nag-workspace
      • Note: Uses c06fcf and friends (extra workspace supplied).
      • Note: Complex data are stored in separate real/imag arrays.
      • Note: forwards and backwards real transforms have the same sign

• NAPACK

  • URL: http://www.netlib.org/napack/ (was valid on Fri Aug 17 23:36:01 EDT 2001)
  • Benchmark label: napack
  • Author: William W. Hager
  • Year: 1987
  • Language: Fortran 77
  • References: William W. Hager, Applied Numerical Linear Algebra (Prentice-Hall, 1987).

• newsplit

  • Author: Steven G. Johnson
  • Email address: stevenj atta alum dotta mit dotta edu
  • Year: 2005
  • Language: C
  • Note: new split-radix method, with symmetric scale factors
  • Note: This is a toy implementation to demonstrate a new version of the split-radix FFT with reduced arithmetic complexity. It is not intended for actual use (being very slow, and lacking an inverse transform).

• Numerical Recipes

  • URL: http://www.nr.com/ (was valid on Fri Aug 17 15:35:44 EDT 2001)
  • Author: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery
  • Benchmarked variants:
    • nr-c
      • Year: 1993
      • Language: C
      • References: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C: The Art of Scientific Computing (Cambridge Univ. Press, 1993).
    • nr-f
      • Year: 1992
      • Language: Fortran 77
      • References: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in Fortran (Cambridge Univ. Press, 1992).

• numutils

  • URL: http://www.atl.external.lmco.com/proj/csim/xgraph/numutil/ (was valid on Sun Dec 1 21:06:34 EST 2002)
  • Author: Carl Hein
  • Email address: chein atta atl dotta lmco dotta com
  • Year: 2002
  • Language: C
  • Note: The forward transform is scaled

• ooura

  • URL: http://momonga.t.u-tokyo.ac.jp/~ooura/fft.html (was valid on Sat Feb 23 09:00:34 EST 2002)
  • Author: Takuya Ooura
  • Email address: ooura atta mmm dotta t dotta u-tokyo dotta ac dotta jp
  • Year: 2001
  • Version: 2001/11/22
  • Note: Inverse real transform is scaled by .5
  • Note: Sign of forward real transform is +1
  • Benchmarked variants:
    • ooura-4f2d
      • Language: C
    • ooura-4f2df
      • Language: Fortran 77
    • ooura-4g
      • Language: C
      • Note: Radix-4 algorithm
    • ooura-4gf
      • Language: Fortran 77
      • Note: Radix-4 algorithm
    • ooura-8g
      • Language: C
      • Note: Radix-8 algorithm
    • ooura-8gf
      • Language: Fortran 77
      • Note: Radix-8 algorithm
    • ooura-sg
      • Language: C
      • Note: Split-radix algorithm
    • ooura-sg2d
      • Language: C
    • ooura-sg2df
      • Language: Fortran 77
    • ooura-sg3d
      • Language: C
    • ooura-sg3df
      • Language: Fortran 77
    • ooura-sgf
      • Language: Fortran 77
      • Note: Split-radix algorithm

• Programs for Digital Signal Processing

  • Language: Fortran 77
  • References: IEEE DSP Committee, Programs for Digital Signal Processing (IEEE Press, 1979). ISBN 0-471-05962-5. (Out of Print)
  • Note: The backward transform is scaled
  • Benchmarked variants:
    • dsp79-FAST
      • Author: G. D. Bergland and M. T. Dolan
      • Year: 1979
      • Note: Subroutine FAST from DSP Section 1.2
    • dsp79-FFA
      • Author: G. D. Bergland and M. T. Dolan
      • Year: 1979
      • Note: Subroutine FFA from DSP Section 1.2
    • dsp79-FFT842
      • Author: G. D. Bergland and M. T. Dolan
      • Year: 1979
      • Note: Subroutine FFT842 from DSP Section 1.2
      • Note: Complex data are stored in separate real/imag arrays.
    • dsp79-morris
      • Author: L. Robert Morris
      • Year: 1979
      • Note: DSP Section 1.8
    • dsp79-rader
      • Author: C. M. Rader, after Brenner
      • Year: 1979, after Brenner 1967
      • Note: DSP Section 1.1
    • dsp79-singleton
      • Author: Richard C. Singleton
      • Year: 1979, derived from Singleton 1968
      • References: R. C. Singleton, An algorithm for computing the mixed radix fast Fourier transform, IEEE Trans. on Audio and Electroacoustics AU-17, no. 2, p. 93-103 (June, 1969).
      • Note: DSP Section 1.4
    • dsp79-wfta
      • Author: James H. McClellan and Hamid Nawab
      • Year: 1979
      • Note: Complex data are stored in separate real/imag arrays.
      • Note: DSP Section 1.7
      • Note: Modified by Matteo Frigo to remove assumption that local variables are SAVEd

• qft

  • Author: Gary A. Sitton
  • Email address: gary dotta sitton atta wg dotta waii dotta com
  • Year: 1994
  • Language: C
  • References: H. Guo, G. A. Sitton, C. S. Burrus, The Quick Discrete Fourier Transform, Proc. ICASSP, April 1994.
  • Note: Received in personal communication with the author.
  • Note: Complex data are stored in separate real/imag arrays.
  • Note: inverse real transform is scaled

• ransom

  • Author: Scott Ransom
  • Email address: ransom atta physics dotta mcgill dotta ca
  • Year: 1997
  • Language: C
  • Note: Received in personal communication with the author.
  • Note: Uses a six-step FFT algorithm. Derived from Mikko Tommila's Apfloat arbitrary-precision arithmetic package, which performed a six-step number-theoretic transform.
  • Note: Backwards transform works by two extra passes to conjugate input and output.

• rmayer

  • URL: http://www.geocities.com/ResearchTriangle/8869/fft_summary.html (was valid on Wed Aug 15 22:39:07 EDT 2001)
  • Author: Ron Mayer
  • Email address: ramayer atta geocities dotta com
  • Year: 1993
  • Language: C
  • Note: Complex data are stored in separate real/imag arrays.
  • Note: Based on the Fast Hartley Transform (FHT).
  • Note: The inverse transform is scaled.
  • Benchmarked variants:
    • rmayer-buneman
      • Note: Uses Buneman stable iterative trigonmetric generator formulas, variant 1.
    • rmayer-buneman2
      • Note: Uses Buneman stable iterative trigonmetric generator formulas, variant 2.
    • rmayer-buneman3
      • Note: Uses Buneman stable iterative trigonmetric generator formulas, variant 3.
    • rmayer-ctrig
      • Note: Uses C sin/cos functions to compute twiddles at runtime.
    • rmayer-lookup
      • Note: Uses table lookup for trigonometric functions (twiddle factors).
    • rmayer-simple
      • Note: Uses simple (somewhat unstable) trigonometric iteration formula, similar to that used in Numerical Recipes and Singleton's FFT.
    • rmayer-unstable
      • Note: Uses unstable trigonometric iteration formula, corresponding to simple complex multiplication of the roots of unity.

• SciMark

  • URL: http://math.nist.gov/scimark2/ (was valid on Tue May 3 22:33:43 EDT 2005)
  • Benchmark label: scimark2c
  • Authors: Roldan Pozo, Bruce Miller
  • Email addresses: pozo atta nist dotta gov, bruce dotta miller atta nist dotta gov
  • Year: 2000
  • Version: 2.0
  • Language: C
  • Note: C version of SciMark Java benchmark.
  • Note: The backwards transform is scaled.

• sciport

  • URL: http://www.netlib.org/scilib/ (was valid on Fri Aug 30 21:09:06 EDT 2002)
  • Author: Scott H. Lamson
  • Language: Fortran 77
  • References: SCIPORT is a portable re-implementation of Cray's SCILIB; developed at General Electric, probably by Scott H. Lamson.
  • Note: Stockham auto-sort FFT, radix-2.
  • Note: Slightly modified to compile properly with g77.

• Silicon Graphics Scientific Mathematical Library (complib.sgimath)

  • Benchmark label: sgimath

• singleton

  • URL: http://www.netlib.org/go/fft.f (was valid on Thu Jul 12 20:26:24 EDT 2001)
  • Author: R. C. Singleton
  • Year: 1968
  • Language: Fortran 77
  • References: R. C. Singleton, An algorithm for computing the mixed radix fast Fourier transform, IEEE Trans. on Audio and Electroacoustics AU-17, no. 2, p. 93-103 (June, 1969).
  • Benchmarked variants:
    • singleton
      • URL: http://www.netlib.org/go/realtr.f
      • Note: Used complex data format (alternating real/imag. parts), which usually seems to be faster than separate real/imag. arrays.
    • singleton-3d

• sorensen

  • Author: Henrik Sorensen
  • Language: Fortran 77
  • Benchmarked variants:
    • sorensen-ctfftsr
      • Year: 1984
      • References: Sorensen, Heideman, Burrus: On computing the split-radix FFT, IEEE Tran. ASSP, Vol. ASSP-34, No. 1, pp. 152-156 Feb. 1986
      • Note: Complex data are stored in separate real/imag arrays.
      • Note: no inverse is provided, although one can easily swap the real and imaginary pointers.
    • sorensen-rsrfft
      • Year: 1985
      • References: Sorensen, Jones, Heideman, Burrus: Real-valued fast Fourier transform algorithms, IEEE Tran. ASSP, Vol. ASSP-35, No. 6, pp. 849-864, June 1987
    • sorensen-sfftfu
      • URL: http://ourworld.compuserve.com/homepages/steve_kifowit/sfftfu.txt (was valid on Mon Jul 16 00:03:31 EDT 2001)
      • Year: 1984
      • References: Electronics Letters, January 5, 1984
      • Note: Complex data are stored in separate real/imag arrays.

• spiral-egner-fft

  • URL: http://www.ece.cmu.edu/~spiral/fft.html (was valid on Sun Sep 1 19:30:13 EDT 2002)
  • Authors: Gavin Haentjens, Adrian Sox
  • Email addresses: gh2r atta andrew dotta cmu dotta edu, asox atta andrew dotta cmu dotta edu
  • Year: 2000
  • Version: 1
  • Language: C
  • Note: Design is based on an FFT package by Sebastian Egner.
  • Note: Backwards transform is forward transform plus two extra passes to scale and reverse the output.
  • Note: Uses codelets (hard-coded FFTs of small sizes, with or without premultiplying twiddle factors) from FFTW 2.1.1.

• StatLib

  • Language: Fortran 77
  • Note: Downloaded from the StatLib repository at Carnegie Mellon University, in the Applied Statistics algorithm collection.
  • Note: The forward transform is scaled.
  • Benchmarked variants:
    • as117
      • URL: http://lib.stat.cmu.edu/apstat/117
      • Author: Donald M. Monro and John L. Branch
      • Year: 1977
      • References: Donald M. Monro and John L. Branch, Algorithm AS 117: The chirp discrete Fourier transform of general length, Appl. Statist. 26 (3), pp. 351-361 (1977).
      • Note: Complex data are stored in separate real/imag arrays.
      • Note: Uses the chirp-z algorithm to compute FFTs of arbitrary size, via the as83 power-of-two FFT.
    • as83
      • URL: http://lib.stat.cmu.edu/apstat/83
      • Author: Donald M. Monro
      • Year: 1975
      • References: Donald M. Monro, Algorithm AS 83: Complex discrete fast Fourier transform, Appl. Statist. 24 (1), pp. 153-160 (1975).
      • Note: Complex data are stored in separate real/imag arrays.
      • Note: The inverse transform is computed via the inverse transform by a pair of complex conjugations.
    • as97
      • URL: http://lib.stat.cmu.edu/apstat/97
      • Author: Donald M. Monro
      • Year: 1976
      • References: Donald M. Monro, Algorithm AS 97: Real discrete fast Fourier transform, Appl. Statist. 25 (2), pp. 166-172 (1976).

• Sun Performance Library (SUNPERF)

  • Benchmark label: sunperf
  • Note: Using new fft interface (CFFTC etc.)

• temperton

  • URL: http://www.caps.ou.edu/ARPS/ (was valid on Mon Jul 16 00:03:31 EDT 2001)
  • Author: Clive Temperton, modified by Russ Rew
  • Year: 1980
  • Language: Fortran 77
  • References: The package was written by Clive Temperton at ECMWF in November, 1978. It was modified, documented, and tested for NCAR by Russ Rew in September, 1980.
  • Note: Can be found online in the ARPS weather-simulator
  • Note: The forward (real->complex) transform is scaled.

• teneyck

  • URL: http://risc2.numis.nwu.edu/ftp/pub/transforms/fftlib.f (was valid on Sat Aug 31 16:37:44 EDT 2002)
  • Author: Lynn F. Ten Eyck
  • Email address: lteneyck atta sdsc dotta edu
  • Year: 1973
  • Language: Fortran 77
  • References: Modified by L. F. Ten Eyck from a one-dimensional version written by G. T. Sande, 1969. L. F. Ten Eyck, Crystallographic Fast Fourier Transforms, Acta Cryst. A29, 183-191 (1973).

• valkenburg

  • URL: http://www.jjj.de/fft/fft2.tgz (was valid on Mon Sep 2 18:10:40 EDT 2002)
  • Author: Peter Valkenburg
  • Email address: p_valkenburg atta hotmail dotta com
  • Year: 1987
  • Language: C
  • Note: The forward transform has two extra passes to conjugate and scale input and output.

• vbigdsp

  • URL: http://findsabrina.org/altivec/ (was valid on Thu Mar 27 20:18:01 EST 2003)
  • Authors: Apple Computer, Inc., Greg Allen
  • Email address: gallen atta arlut dotta utexas dotta edu
  • Year: 2003
  • Version: 20030322
  • References: R. Crandall and J. Klivington, Supercomputer-style FFT library for Apple G4, Apple Technical Report (Jan. 2000).
  • Note: Sample code provided by Apple, modified by Greg Allen to work on Linux/PowerPC.
  • Note: Apple's description: Though arbitrary signal lengths (i.e. all powers of 2) are handled, our design emphasis is on very long signals (length N >= 2^16 and on into the millions), for which cache considerations are paramount. The core of the library is a particular variant of full-complex FFT that for signal length N = 2^10 executes at 1.15 giga ops (500 MHz G4). This cache-friendly, core FFT plays a dominant role in the long-signal cases such as two-dimensional FFT and convolution. More important perhaps than the core performance benchmark is the manner in which one can sift through the myriad prevailing (and new) FFT frameworks, to arrive at a suitable such framework for the Velocity Engine.

• vdsp

  • URL: http://developer.apple.com/techpubs/macosx/CoreTechnologies/vDSP/vDSP.html (was valid on Tue Jul 17 23:01:08 EDT 2001)
  • Author: Apple Computer, Inc.
  • References: R. Crandall and J. Klivington, Supercomputer-style FFT library for Apple G4, Apple Technical Report (Jan. 2000).
  • Note: Part of Apple's vecLib, this library is designed for use with the AltiVec SIMD instructions on a PowerPC G4.
  • Note: The forward real transform is scaled by 2.
  • Note: Complex data are stored in separate real/imag arrays.
  • Note: Real data are split into even/odd arrays.