Examples of convolution using FFT
Another thing we learn in class, also related to FFTs,
is how an N point DFT (multiplication by an N by N matrix)
can be broken down into two N/2 point DFTs (each of which is
a multiplication by an N/2 by N/2 matrix). Here, for example,
the 8 by 8 matrix multiply is reduced to two 4 by 4 matrix multiplies:
(above image is linked to the idraw source file; you can edit this image
using idraw).
The triangles in the above image denote amplifiers, i.e. multiplication
by a constant. The exponent next to each amplifier denotes the
number of times it's applied, e.g. the triangle raised to exponent k denotes
Wk.