multiplication of large multivariate polynomials
- To: mathgroup at smc.vnet.net
- Subject: [mg105551] multiplication of large multivariate polynomials
- From: palacian at unavarra.es
- Date: Tue, 8 Dec 2009 06:45:00 -0500 (EST)
I have to multiply multivariate homogeneous polynomials in 8 variables, say f and g, such that the total degree of f*g can be up to 30 or 32. The coefficients are in general complex numbers, sometimes in exact precision and on some ocassions, floating-point numbers. The polynomials are somehow sparse (for instance if f is a multivariate homogeneous polynomial of degree 14, out of 116280 possible monomials it usually has about 25560 monomials). I need to do many multiplications of this sort within Mathematica, thus I would like to speed up my computations. I have programmed a sort of Karatsuba routine for multivariate polynomial but Expand[f*g] works better. I also usede the Kronecker trick, passing to a multiplication of univariate polynomials through a map, and inverting the map getting the desired product f*g. By doing so, using recursion and storing in the stack the intermediate results of the univariate multiplications I could get a good performance of the Kronecker procedure with an overall timing better than the standard multiplication with Expand[f*g]. However, the problem with the evaluation stack is that the amount of memory used grows up enormously, making the whole process slower than the one using Expand[f*g]. I wonder if I could handle the multiplications using the list representation of the polynomials and convolutions. I tried through the functions CoefficientList[] and ListConvolve[] but it does not work well for large polynomials. Nevertheless I guess that I could take advantange of the fact that the polynomials are homogeneous, so a shorter representation of the polynomial as lists combined with a clever use of ListConvolve[] would make the computations much faster. Do you have any clue of how to tackle this? I would appreciate your help. Thanks in advance, Jesus