2. Fast Fourier transforms

where is one of the roots of unity . The definition in Eq. 1 is simply a premultiplication of the vector with elements by a matrix with elements , and this multiplication requires operations.

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

in which we use the result and introduce the notation and to represent the even and odd elements respectively. Equation 2 shows that a DFT of length may be rewritten as the combination of two DFTs of length . This lemma may be applied recursively, as long as the length of the DFT remains even, so that if 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 operations, and this is the (radix-2) FFT. The lemma may be generalised to apply when contains factors other than 2.

In three dimensions, the definition of the DFT is