FFTW - Fastest Fourier Transform in the West
The Fourier transform is a mathematical operation that allows you to decompose a function into oscillatory functions. It is used to transform a signal into its characteristic frequencies. Fast algorithms for discrete Fourier transforms are essential for high performance computing. Although the most trivial algorithm to calculate a Fourier transform requires O(N2) operations, the fast Fourier transform does it in O(N log N) operations. For larger numbers, this difference becomes enormous.
The FFTW library (for Fastest Fourier Transform in the West), allows the realization of these operations. It supports serial computations, threaded computations, and MPI. Two major versions of FFTW are available: FFTW2 and FFTW3. These two versions are incompatible and their interfaces are different. FFTW2 is now considered obsolete and has not been updated since 1999.
To get to know the versions that are installed on the server that you are using, run this command:
[name@server $] module avail 2>&1 | grep -i fftw
Intel's MKL library included its own version of FFTW which is optimized for Intel processors.
A performance test was done on Colosse to compare the performance of different FFTW versions. The tested versions are:
- FFTW, version 3.2.2 - an open source library (available for Intel and GCC compilers);
- FFTW, version 2.1.5 - the previous version of FFTW, for compatibility with applications that have not been changed to use FFTW 3.x (available for Intel and GCC compilers);
- MKL - Math Kernel Library offers a highly optimized implementation of discrete Fourier transforms.
Here is an observation of the performance of the various libraries for a Fourier transform in one dimension. This is the first test of the test suite BenchFFT, done on Colosse in the form on serial jobs.
Source code for an example
The following file contains an example of a Fourier transform computation into cosine functions for a real function. The code is written in Fortran 90: