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][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

``` ```