Fastest Fourier Transform in the West (FFTW)
FFTW is allegedly the Fastest Fourier Transform in the West. The package was developed by Matteo Frigo and Steven G. Johnson at MIT and is free software. It consists of C-routines that are accessible via a library archive, and may be used from both C and Fortran programs. The routines have the ability to adopt their algorithm to size and type of the required Fourier transform, as well as to the type of machine on which they are executed. Additionally FFTW provides shared-memory parallelism via multithreading.