FFTW

The "Fastest Fourier Transform in the West" (FFTW) is a C library for computing discrete Fourier transforms (DFT). Note that there are two main versions of FFTW, version 2 and version 3 which are not compatible. The basic usage of FFTW to compute a one-dimensional DFT of size N is simple, and it typically looks something like this code:

     #include <fftw.h>
     ...
     {
         fftw_complex *in, *out;

         fftw_plan p;
         ...
         in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);

         out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);

         p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);

         ...
         fftw_execute(p); /* repeat as needed */
         ...
         fftw_destroy_plan(p);

         fftw_free(in); fftw_free(out);
     }

Other examples can be found in the FFTW documentation.