On the bit-complexity of sparse polynomial and series multiplication

• Published in: Journal of symbolic computation 2013-03, Vol.50, p.227-254
• Main Authors: van der Hoeven, Joris, Lecerf, Grégoire
• Format: Article
• Language: English
• Subjects: Algorithm; Computer Science; Mathematical Software; Multi-point evaluation; Polynomial factorization; Power series; Sparse multiplication
• ISSN: 0747-7171; 1095-855X
• DOI: 10.1016/j.jsc.2012.06.004

In this paper we present various algorithms for multiplying multivariate polynomials and series. All algorithms have been implemented in the C++ libraries of the Mathemagix system. We describe naive and softly optimal variants for various types of coefficients and supports and compare their relative performances. For the first time, under the assumption that a tight superset of the support of the product is known, we are able to observe the benefit of asymptotically fast arithmetic for sparse multivariate polynomials and power series, which might lead to speed-ups in several areas of symbolic and numeric computation. For the sparse representation, we present new softly linear algorithms for the product whenever the destination support is known, together with a detailed bit-complexity analysis for the usual coefficient types. As an application, we are able to count the number of the absolutely irreducible factors of a multivariate polynomial with a cost that is essentially quadratic in the number of the integral points in the convex hull of the support of the given polynomial. We report on examples that were previously out of reach.