2. Fast Fourier transforms

For a full description of the FFT see, for example Ref. [5]. We consider a vector of length $n$ with elements $x_k$ where $0 \leq k < n$. The elements of the discrete Fourier transform (DFT) of this vector, $X_k$, may then be defined by

$$X_k = \sum_{j=0}^{n-1} \omega_{n}^{k j} x_j$$ (1)

where $\omega_{n}$ is one of the ${n}^{\mathrm{th}}$ roots of unity $\omega_n = \exp(-2 \pi \mathrm{i}/ n)$. The definition in Eq. 1 is simply a premultiplication of the vector with elements $x_j$ by a matrix with elements $F_{kj} = \omega_n^{k j}$, and this multiplication requires $O(n^2)$ operations.

Consider the following result, known as the Danielson-Lanczos lemma [6], applied to Eq. 1 for even $n=2m$:

$$X_k = \sum_{j=0,~\mathrm{even}}^{n-1} \omega_n^{k j} x_j + \sum_{j=0,~\mathrm{odd}}^{n-1} \omega_n^{k j} x_j$$

$$= \sum_{j'=0}^{m-1} \omega_n^{k (2j')} x_{2j'} + \sum_{j'=0}^{m-1} \omega_n^{k (2j'+1)} x_{2j'+1}$$

$$= \sum_{j'=0}^{m-1} \omega_m^{k j'} x^{\mathrm{e}}_{j'} + \omega_n^k \sum_{j'=0}^{m-1} \omega_m^{k j'} x^{\mathrm{o}}_{j'}$$ (2)

in which we use the result $\omega_n^{2k} = \omega_{n/2}^k$ and introduce the notation $x^{\mathrm{e}}_k = x_{2k}$ and $x^{\mathrm{o}}_k = x_{2k+1}$ to represent the even and odd elements respectively. Equation 2 shows that a DFT of length $n$ may be rewritten as the combination of two DFTs of length $n/2$. This lemma may be applied recursively, as long as the length of the DFT remains even, so that if $n$ is a power of 2, it may be applied until the trivial DFT of a vector of length 1 is required. In this case, the DFT requires only $O(n \log_2 n)$ operations, and this is the (radix-2) FFT. The lemma may be generalised to apply when $n$ contains factors other than 2.

In three dimensions, the definition of the DFT is

$$X_{k_x k_y k_z} = \sum_{j_x=0}^{n_x-1} \omega_{n_x}^{k_x j_x... ...y} \sum_{j_z=0}^{n_z-1} \omega_{n_z}^{k_z j_z} x_{j_x j_y j_z}$$ (3)

Equation 3 demonstrates that the three-dimensional DFT is the product of 3 one-dimensional DFTs which all commute with each other since they act indepedently.