Fast Fourier Transform Software

The Fast Fourier Transform (FFT) is the fast algorithm to compute the Discrete Fourier Transform. Various FFT software packages are available with differing speeds and workspace requirements.

IBM Engineering and Scientific Subroutine Library (ESSL) (IBM SP): The ESSL library contains Fourier Transform routines that perform mixed-radix transforms in one, two, and three dimensions. For information on available subroutines and their usage see: ESSL Fourier Transforms Subroutines.
IBM Parallel Engineering and Scientific Subroutine Library (PESSL) (IBM SP): The Parallel ESSL Library supports the Single Program Multiple Data (SPMD) programming model using the Message Passing Interface (MPI). The Fourier transform subroutines in PESSL perform mixed-radix transforms in two and three dimensions. For information on available subroutines and their usage see PESSL Fourier Transforms (Message Passing).
FFTW (IBM SP): FFTW is a portable, free, high performance DFT library which implements arbitrary radix, serial and multiple dimensional transforms in serial or parallel (MPI and POSIX threads models). One unique aspect of FFTW is its optional use of self-optimizing strategies, whereby subsequent calls become faster by building on previous timings. Wrapper functions provide a Fortran API to this native C library.
NAG (IBM SP): The NAG library provides several FFT routines for FFT which work either "in place" (i.e. saving memory) or with workspace arrays (which saves time). Inverse transforms can also be obtained. For information on available subroutines and their usage see: C06-Summation of Series.
IMSL (Jacquard): FFTs in IMSL are modeled on the Cooley-Tukey algorithm. Three separate subroutines are provided for FFT initialization and for computing forward and backward transforms. For more information on available subroutines and their usage see: Alphabetized list of the IMSL Fortran 77 math libraries and IMSL Math/Library Online User's Guide.

The following table gives some basic information about the FFT routines supported in libraries IBM ESSL/PESSL, NAG and IMSL. Each library has its own strengths and limitations. This table points to the most suitable library, depending on type of transform and various other requirements. The table is divided into four groups depending on the dimensionality of the FFT. They are:

One-Dimensional FFT - calculates one FFT in one dimension.
Multiple one-dimensional FFT - calculates an FFT in one dimension for each column of a two-dimensional array.
Two-Dimensional FFT - calculates one FFT in two dimensions.
Three-Dimensional FFT - calculates one FFT in three dimensions.

Abbreviations
Notation	Meaning
C-to-C	Library contains Complex-to-Complex transforms
C-to-R	Library contains Complex-to-Real transforms
R-to-C	Library contains Real-to-Complex transforms
I	Library contains Inverse transforms
P	Library contains Parallel transforms
S	Library supports non-unit Stride input
	Library does not contain such transforms
N	Number of transform data values

Summary of FFT software

One-dimensional FFT

Type of Transform	NAG	IMSL	FFTW
C-to-C	I	I	I,S,P
R-to-C	I	I	I,S,P
C-to-R			I,S,P

Multiple One-dimensional

Type of Transform	ESSL	PESSL	NAG	FFTW
C-to-C	I,S	I,S,P	I	I,S,P
R-to-C	I,S	I,S,P	I	I,S,P
C-to-R	I,S	I,S,P		I,S,P

Two-dimensional

Type of Transform	ESSL	PESSL	NAG	IMSL	FFTW
C-to-C	I,S	I,S,P	I	I	I,S,P
R-to-C	I,S	I,S,P			I,S,P
C-to-R	I,S	I,S,P			I,S,P

Three-dimensional

Type of Transform	ESSL	PESSL	NAG	IMSL	FFTW
C-to-C	I,S	I,S,P	I	I	I,S,P
R-to-C	I,S	I,S,P			I,S,P
C-to-R	I,S	I,S,P			I,S,P

The table below gives length restrictions for N and workspace requirements based on one-dimensional complex-to-complex FFTs in libraries IBM ESSL, NAG and IMSL.

Note: The FFT performance for a given value of N depends on the prime factorization of N. Fastest performance is realised for values of N that are products of powers of 2, 3 and 5.

Library	N Length Restrictions	Workspace Requirements
ESSL	N = (2^h)(3ⁱ)(5^j)(7^k)(11^m) for N <= 37748736 where: h = 1, 2, ..., 25 i = 0, 1, 2 j, k, m = 0, 1	2.28N + 40000 for N > 8192 40000 for N <= 8192 Also see: ESSL Documentation
NAG	N = (2^g)(3^h)(5ⁱ)(7^j)(11^k)(13^l)(17^m)(19ⁿ) where: g+h+i+j+k+l+m+n < 20	none; `N` for greater speed
IMSL	None	6N+15
FFTW	None FFTW is best at handling sizes N = 2^a 3^b 5^c 7^d 11^e 13^f, where e+f is either 0 or 1, and the other exponents are arbitrary. Other sizes are handled by a general O(n lg n) routine.	none; N for greater speed; N=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32, 64 can be done fast in place.

HPC Users

HPC Resources

Software