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.


Virginie Collette
Last modified: Fri Mar 5 18:39:37 CET 2004