The Truncated Fourier Transform
Paul Vrbik, University of Western Ontario.Wednesday June 2nd, in K9509 at 3:30pm.
Abstract. 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.