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

```
```