  In this paper, we present fast algorithms for the product of two multivariate
polynomials in sparse representation. The bit complexity of our algorithms are
studied in detail for various types of coefficients, and we derive new
complexity results for the power series multiplication in many variables. Our
algorithms are implemented and freely available within the Mathemagix software.
We show that their theoretical costs are well-reflected in practice.

Data Structures and Algorithms;Mathematical Software