On the bit-complexity of sparse polynomial and series multiplication (Q1930169)

The authors compare several classical and new algorithms for the multiplication of multivariate polynomials and power series regarding their asymptotic complexity. It is assumed that the support of the product is known or has a known bound. Often to know the support of the coefficients in the product is the most difficult part for sparse representations. So the emphasis is on the computation of the coefficients of the product. First classical algorithms for sparse and dense polynomials are recalled, including the Kronecker substitution technique as well as a naive algorithm for the multiplication of power series. Then a discussion is given for the sparse multiplication of polynomials for different possible coefficient fields (finite field, integers, rationals, floating point,\dots). For dense truncated power series (which may be considered as sparse infinite series), also the support is known, and efficient algorithms exist. Finally a section is devoted to counting the number of absolutely irreducible factors. All the algorithms are analyzed for their asymptotic complexity, but they are also implemented in C++ and tables with timings are included. Because of the many components of the methods, there is still room for improvement by fine tuning.