In this paper, we present a truncated version of the classical Fast Fourier Transform. When applied to polynomial multiplication, this algorithm has the nice property of eliminating the “jumps” in the complexity at powers of two. When applied to the multiplication of multivariate polynomials or truncated multivariate power series, we gain a logarithmic factor with respect to the best previously known algorithms.

Keywords: fast Fourier transform, jump phenomenon, truncated multiplication, FFT-multiplication, multivariate polynomials, multivariate power series

A.M.S. subject classification: 42-04, 68W25, 42B99, 30B10, 68W30

View: Html, TeXmacs, Pdf, BibTeX

Note: an annoying mistake concerning the multivariate version has been corrected in a follow-up paper