Re: multiplication of large multivariate polynomials
- To: mathgroup at smc.vnet.net
- Subject: [mg105598] Re: multiplication of large multivariate polynomials
- From: dh <dh at metrohm.com>
- Date: Thu, 10 Dec 2009 04:58:42 -0500 (EST)
- References: <hfledp$sl4$1@smc.vnet.net>
Hi Jesus,
the homogeneity may be used to eliminate one dimension of the problem.
that is, you represent only 7 of your 8 variables.
To keep the example simple, we assume that we have a homogeneous
polynomial of 3 variables.
Assume we represent the terms of a polynomial by triplets:
{coefficient, exponent of first variable, exponent of second variable}
The exponent of the third variables is then given by homogeneity.
To obtain the product of two polynomials p1 and p2, we need to multiply
each term of p1 with each term of p2. This can be done by Outer:
E.g.:
p1 = RandomInteger[{0, 9}, {5, 3}]
p2 = RandomInteger[{0, 9}, {5, 3}]
t = Outer[{#1[[1]] #2[[1]], #1[[2]] + #2[[2]], #1[[3]] + #2[[3]]} & ,
p1, p2, 1];
Flatten[t, 1]
Daniel
palacian at unavarra.es wrote:
> 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
>
>