Go back to the benchmark results.

# FFT Software Used

Note: Many of the publicly-available FFT subroutines are written in Fortran. These were converted to C via f2c for inclusion in the benchmark.

## One-Dimensional Fourier Transforms

The following are the codes that were used in the one-dimensional benchmark, along with the abbreviations that are used for them in the performance graphs.
• cilk_fft: This FFT is a precursor to FFTW, written by Matteo Frigo (one of the FFTW authors). A major advantage of this code is that, on parallel machines with Cilk installed, it will get a linear speedup (it also runs on sequential machines with standard C compilers). This code is especially optimized for N's which are powers of two, although it works for any N.
• FFTW: The one-dimensional routines from the FFTW 1.1 package.
• We benchmarked two versions of this routine. The first one computes the optimal decomposition of the array by actually making timing measurements. The second version uses a heuristic and is labeled FFTW_ESTIMATE.
• CWP: A Prime Factor Algorithm (PFA) FFT implemenation from a C numerical library by the Colorado School of Mines. (More info here.) In some sense, this routine "cheats"--it requires that you give it an array size which it can transform quickly. Thus, it usually was running on a slightly larger array than the other codes. We ran two versions of CWP:
• CWP (min N): use the minimum allowable N greater than or equal to the N used by the rest of the FFTs.
• CWP (optimal N): use the optimal allowable N greater than or equal to the N used by the rest of the FFTs.
• ffts in C: A heavily inlined & optimized C FFT by Richard H. Krukar. (Here is his spartan home page.) This FFT can only handle N's which are powers of 2 (and no greater than 4096).
• mixfft: A mixed-radix C FFT written by Jens Jorgen Nielsen.
• GO: A Fortran mixed-radix FFT from the GO (Golden Oldies) library, by R. C. Singleton, Stanford Research Institute, Sept. 1968. The same subroutine actually does N-dimensional FFTs. This code is actually amazingly fast considering its age and N-dimensional generality. (We used a version of the code that was converted from Fortran via f2c. We also tried a version that had been hand-translated, but this had only a negligible effect on the performance.)
• FFTPACK: A well-known library of Fortran FFTs written by P. N. Swarztrauber, available at Netlib.
• NR: This is an FFT from Numerical Recipes in C. It only works for arrays whose sizes are powers of 2. (Not in the public domain.)
• GPFA: A Fortran FFT from "A Generalized Prime Factor FFT Algorithm For Any N = 2P3Q5R," by C. Temperton, J. Sci. Stat. Comp., May 1992.
• NAPACK: A Fortran FFT from the NAPACK package.
• fft2: A C FFT implementing the Cooley-Tukey algorithm, written by "Pjotr." (The full name of the author is unknown.)
• Mayer: A C FFT/FHT by R. Mayer. Can only handle N's that are powers of 2.
• Duhamel: C code implementing a Duhamel-Holman split-radix FFT, written by D. Edelblute and modified by R. Mayer. (See Electronics Letters, January 5, 1984.) Can only handle N's that are powers of 2.
• Beauregard: Yet another C FFT, this one by G. Beauregard. Can only handle N's that are powers of 2.
• ESSL: A highly optimized FFT for the RS/6000 only from IBM's ESSL library. (Not in the public domain.)
• SCILIB: A Cray-provided FFT from Cray's SCILIB library. This routine is highly vectorized on the C90. (Not in the public domain.)
• SUNPERF: The one-dimensional double-precision FFT from the Sun Performance Library, optimized for the UltraSPARC. This code is actually an optimized version of FFTPACK. (Not in the public domain.)

## Three-Dimensional Fourier Transforms

The following are the codes that were used in the three-dimensional benchmark, along with the abbreviations that are used for them in the performance graphs.
• FFTWND: The multi-dimensional routines from the FFTW 1.1 package. We ran two different versions of this code: one for in-place and one for out-of-place transforms.
• GO: An N-dimensional Fortran mixed-radix FFT from the GO (Golden Oldies) library, by R. C. Singleton, Stanford Research Institute, Sept. 1968.
• PDA: Fortran FFT from the PDA (Public Domain Algorithms) library. The 1D FFTs it uses are based on FFTPACK at Netlib.
• NR: A multi-dimensional FFT in C from Numerical Recipes in C. This routine only works for arrays whose dimensions are powers of two. (Not in the public domain.)
• HARMD: Yet another public-domain N-dimensional Fortran FFT. This routine also only works for arrays whose dimensions are powers of two. (The author is unknown.)
• GPFA: A 3D Fortran FFT from "A Generalized Prime Factor FFT Algorithm For Any N = 2P3Q5R," by C. Temperton, J. Sci. Stat. Comp., May 1992.
• ESSL: A highly optimized 3D FFT for the RS/6000 only from IBM's ESSL library. (Not in the public domain.) Only the single-precision version of this routine was available to us, so we compared it separately to a single-precision version of FFTW. (Not in the public domain.)
• SCILIB: A Cray-provided 3D FFT from Cray's SCILIB library. This routine is highly vectorized on the C90. (Not in the public domain.)

Go back to the benchmark results.