FFTCN: Multi-Dimensional Complex Fourier Transforms

Actually once you understand fftc1 there is virtually nothing else left to fftcn. A multi-dimensional Fourier transform simply consists of successive one-dimensional transforms in every dimension. So all fftcn does is loop through the dimensions calling fftc1. The only tricky part about doing this is setting all the right skips correctly. For example, consider the middle dimension of a three dimensional array of size $\{N1,N2,N3\}$. Each DFT will be of length $N2$ and there will be $N1\times N3$ of them. The skip between successive elements of the transform will be $N1$. There will be $N1$ transforms beginning at the elements $0,1,...,N1-1$ but the next one will begin at $N1\times N2-1$. All of these stepsizes and skips are kept track of automatically by fftcn, and following the code itself is probably easier than following any explanation I could write of it.

Inverse transforms are done exactly the same as forward ones, only with all the calls to fftc1 being made for inverse transforms.