Fastest Fourier Transform in the West, is a C library for computing the Discrete Fourier Transform (DFT) in one or more dimensions, of arbitrary input size, and of both real and complex data. Developed at MIT, it is by far the fastest implementation of FFT algorithm (upheld by regular benchmarks.)
module spider FFTW to find out what environment modules are available for this application.
If you publish research that uses FFTW you may want to cite it as follows:
"A Fast Fourier Transform Compiler," by Matteo Frigo, in the Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '99), Atlanta, Georgia, May 1999