The Truncated Fourier Transform

Paul Vrbik, University of Western Ontario.

Wednesday June 2nd, in K9509 at 3:30pm.


The Fast Fourier Transform is an amazingly useful and ubiquitous algorithm in
symbolic and numeric computation. However, it makes the (rather unrealistic)
assumption that the length of it's input vector is a power of two.
The motivation behind the Truncated Fourier Transform (TFT) is the
observation that many computations are wasted because of this. 

TFT is a variation of the Fast Fourier Transform (FFT) that allows one to work
with input vectors that are *not* a power of two. 
I summarize (and correct some mistakes from) the seminal works of Joris 
van der Hoeven's papers. I also expand upon the development of the
inverse TFT in order to make it's description as clear as possible.