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.
arXiv comment8 pages, submitted to the 38th International Symposium on Symbolic and Algebraic Computation (ISSAC 2013)