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.