Here is my collection of notes on the C library FFTW and some applications in which I need it for. Much comes from the documentation available here. The code is available here

General Notes

• To compile use the options -lfftw3 -lm
• FFTW does not normalise so make sure to divide by N^d
• FFTW defines its own (double)complex number class which can be acccessed by array[i],array[i] for real and complex components respectively

1D problems

• FFTW stores co-efficients in the following manner

[0,1,2,...,N/2-1,0,-N/2+1,...,-1]

where the N/2 co-efficient is set equal to 0 (see Spectral Methods in MATLAB). If we have real data, then we only need to store a co-efficient array of size N/2+1 since we have symmetry in the Fourier co-efficients. Thus if we wanted to compute the first derivative we would have something like

for(i=0;i<(N/2+1);i++) {
tmp=out[i];
out[i]=-k[i]*out[i];
out[i]=k[i]*tmp;
}

which multiples by ik. See 1d_real_fft.c for example.

2D problems

• Creators recommend using the following for allocating a 2D matrix

array=(fftw_complex*)fftw_malloc(N*M*sizeof(fftw_complex))

using an array of pointers will cause FFTW to fail. See C FAQ for more information (understand this a bit better)
• To get around the above define macros of the form

#define ind(i,j) (i-1)*N+(j-1)

to get the correct index element. Also uses the more useful convention that matrices use indexing i,j=1,...,n
• We want to take the 2D FFT of a real matrix of size NxN. We define the complex matrix to be of size N x (N/2)+1 with the arrangement going something like