MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Re: variable number of controls in manipulate
  • Next by Date: Re: Rectangle and Circle
  • Previous by thread: Re: Rectangle and Circle
  • Next by thread: Re: multiplication of large multivariate polynomials