FFTW (Fastest Fourier Transform in the West) is a collection of fast C routines for computing the Discrete Fourier Transform in one or more dimensions.

See http://www.fftw.org/ for more details.

There are many libraries available - single/double precision, real/complex, threaded/unthreaded, statically linked/dynamically linked. List them all with the command

ls -l /usr/lib64/lib*fftw*

Note that on an SMP machine, the use of threaded libraries should increase performance.