In a previous paper, we introduced 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, a non-trivial asymptotic factor was gained with respect to the best previously known algorithms.

In the present note, we correct two errors which slipped into the previous paper and we give a new application to the multiplication of polynomials with real coefficients. We also give some further hints on how to implement the TFT in practice.

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