The Fastest Fourier Transform in the West. MIT-LCS-TR-728

This paper describes FFTW, a portable C package for computing the one- and multidimen-sional complex discrete Fourier transform (DFT). FFTW is typically faster than all other publicly available DFT software, including the well-known FFTPACK and the code from Numerical Recipes. More interestingly, FFTW is competitive with or better than propri-etary, highly-tuned codes such as Sun’s Performance Library and IBM’s ESSL library. FFTW implements the Cooley-Tukey fast Fourier transform, and is freely available on the Web a