Fast Multivariate Power Series Multiplication in
Characteristic Zero

G. Lecerf 1 ´ E. Schost2


1 UMR 8100 CNRS, Laboratoire de Math´ematiques, Universit´e de Versailles
St-Quentin-en-Yvelines, 45, avenue des ´Etats-Unis, 78035 Versailles, France.
lecerf@math.uvsq.fr
2 FRE 2341 CNRS, Laboratoire GAGE, Ecole polytechnique, 91128 Palaiseau,
France. schost@gage.polytechnique.fr

 

Abstract
Let k be a field of characteristic zero. We present a fast algorithm for
multiplying multivariate power series over k truncated in total degree. Up
to logarithmic factors, its complexity is optimal, i.e. linear in the number
of coeffcients of the series.
Keywords. Multivariate power series, fast multiplication, complexity.