Multivariate Power Series Multiplication

E. Schost


We study the multiplication of multivariate power series. We show that over large enough fields, the bilinear complexity of the product modulo a monomial ideal M is bounded by the product of the regularity of M by the degree of M. In some special cases, such as partial degree truncation, this estimate carries over to total complexity. This leads to complexity improvements for some basic algorithms with algebraic numbers, and some polynomial system solving algorithms.