Go back to the benchmark results.

**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**.

- 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
**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 = 2^{P}3^{Q}5^{R}," 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.)

**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 = 2^{P}3^{Q}5^{R}," 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.