Fast Fourier Transform is a Discrete Fourier Transform calculated
more efficiently. In order to evaluate the Discrete Fourier Transform
Vandermonde matrix the way we have done it in the previous section
we needed to evaluate somewhat less than
terms because
the first row and the first column are all ones. But certain economies
can be attempted. This derives
from the observation that

is periodic in

It transpires that in order to evaluate a discrete Fourier Transform all that's needed is to evaluate . Then you just need to insert those terms cleverly in appropriate places in the Vandermonde matrix - also, observe that matrix (2.10) is symmetric. Now the insertion of into appropriate spots is not going to be free: those places have to be computed one way or the other and data may have to be moved around too. But the resulting algorithm is not going to be . It is going to be instead.

Consider matrix given by (2.10). Let us rearrange the columns of the matrix
and the entries of the corresponding vector *f*_{k} in the following way:

i.e., we put all the odd columns first and then the even ones. So now the matrix looks as follows:

Now, observe that

and that

(2.13) |

is a Vandermonde matrix for the 4-point discrete Fourier transform, and that multiplications in equation (2.12) can be expressed as:

(2.14) |

Last, observe that the lower right corner of is simply because

(2.15) |

and .

In summary equation (2.11) can be rewritten as follows:

Applying the same reasoning to
^{4}**F**(**f**_{[1:8:2]}) and
to
^{4}**F**(**f**_{[2:8:2]}) we can write without much further ado:

And we repeat it once more to get:

where I have made use of the fact that

And this is Fast Fourier Transform.

When it comes to coding this algorithm, you can either start from the top and then write a recursive procedure, or you can start at the bottom and evaluate four 2-point transforms first, then two 4-point transforms and finally the single 8-point transform.

Observe that you never really evaluate and store the
full Vandermonde discrete Fourier tranform matrix.
Matrices
^{2k}**D**_{k} are diagonal, so they
can be stored simply as vectors and the matrix operation
that converts two *n*-point transforms into one 2*n*-point
transform can be implemented as two simple equations.
The only
terms
that are evaluated while calculating
^{2k}**D**_{k},
are the ones that are really needed. Periodicity of
is automatically taken care of.

- A Recursive Implementation of the Fast Fourier Transform
- The Danielson Lanczos Algorithm
- Fast Fourier Transform in Parallel
- One Dimensional Parallel Fast Fourier Transform
- Exercise