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
the first row and the first column are all ones. But certain economies
can be attempted. This derives
from the observation that
Consider matrix given by (2.10). Let us rearrange the columns of the matrix
and the entries of the corresponding vector fk in the following way:
In summary equation (2.11) can be rewritten as follows:
Applying the same reasoning to
4F(f[2:8:2]) we can write without much further ado:
And we repeat it once more to get:
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 2kDk are diagonal, so they can be stored simply as vectors and the matrix operation that converts two n-point transforms into one 2n-point transform can be implemented as two simple equations. The only terms that are evaluated while calculating 2kDk, are the ones that are really needed. Periodicity of is automatically taken care of.