Séminaire du 17 mai 04, Joris Van Der Hoeven.

The Truncated Fourier Transform and Applications

In this talk, 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.