A new Truncated Fourier Transform algorithm
arXiv:1210.4960
Abstract
Truncated Fourier Transforms (TFTs), first introduced by Van der Hoeven, refer to a family of algorithms that attempt to smooth "jumps" in complexity exhibited by FFT algorithms. We present an in-place TFT whose time complexity, measured in terms of ring operations, is comparable to existing not-in-place TFT methods. We also describe a transformation that maps between two families of TFT algorithms that use different sets of evaluation points.
8 pages, submitted to the 38th International Symposium on Symbolic and Algebraic Computation (ISSAC 2013)