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][0],array[i][1] 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][0];
out[i][0]=-k[i]*out[i][1];
out[i][1]=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