One package that I use often is the FFTW, a C subroutine library for computing the Discrete Fourier Transform (DFT), from http://www.fftw.org/. It has a very high benchmark, see http://www.fftw.org/benchfft/ for more info, and I highly recommend it. It is GPLed. Please take a look.