MathGroup Archive 2007

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

Search the Archive

Re: speed of multiplying polynomials


On Jan 6, 11:28 pm, dmhar... at math.harvard.edu wrote:
> I'm trying to figure out how fast mathematica can multiply polynomials
> with integer coefficients.

Depends how you do it.  Here's very simple way to
multiply polynomials.

poly := Sum[Random[Integer, {1, 1000}]*x^i, {i, 0, 1000}];
SeedRandom[1];
Expand[poly*poly]; // Timing

{1.20313 Second, Null}


On the other hand, suppose we represent a polynomial
as a list; then, we can use ListConvolve.

listpoly := Table[Random[Integer, {1, 1000}], {1001}];
SeedRandom[1];
ListConvolve[PadRight[listpoly, 2001],
  PadRight[listpoly, 2001], 1]; // Timing

{0.002973 Second, Null}

About 400 times faster.

You can remove the semi-colons to examine the output and
see that the results are equivalent.

Lists are a fundamental data structure and in this case
we are able to express the desired object using a list and
we can express the operation using a command which acts
on Lists.  Symbolic manipulation, by contrast, is likely
to be much slower.

Mark


  • Prev by Date: Replacements in NonCommutativeMultiply
  • Next by Date: Re: speed of multiplying polynomials
  • Previous by thread: Re: speed of multiplying polynomials
  • Next by thread: Re: speed of multiplying polynomials