Prev: Minimization with constraint expresses as CDF[] >=
Next: pursuit curve (differential equations)
From: dmharvey on 6 Jan 2007 23:28
Hi,

I'm trying to figure out how fast mathematica can multiply polynomials
with integer coefficients. I don't know mathematica well at all, but I
had a friend write me a mathematica program to test this. It look like
on a regular desktop machine it can multiply e.g. degree 1000
polynomials with coefficients in the range 0 <= x <= 1000 in about 1.3
seconds.

This is ludicrously slow compared to some other computer algebra
systems, which can do this multiplication in about 0.0003
seconds. I can't believe mathematica is in the order of 10000 times
slower for this simple task. I think perhaps we are doing something
wrong. Can anyone suggest a way of coaxing mathematica into doing this
kind of arithmetic at a comparable pace?

Many thanks

David

From: Roman Pearce on 8 Jan 2007 04:55
dmharvey(a)math.harvard.edu wrote:
> I'm trying to figure out how fast mathematica can multiply polynomials
> with integer coefficients. I don't know mathematica well at all, but I
> had a friend write me a mathematica program to test this. It look like
> on a regular desktop machine it can multiply e.g. degree 1000
> polynomials with coefficients in the range 0 <= x <= 1000 in about 1.3
> seconds.
>
> This is ludicrously slow compared to some other computer algebra
> systems, which can do this multiplication in about 0.0003
> seconds. I can't believe mathematica is in the order of 10000 times
> slower for this simple task. I think perhaps we are doing something
> wrong. Can anyone suggest a way of coaxing mathematica into doing this
> kind of arithmetic at a comparable pace?

The speed will depend heavily on the representation of the polynomials and
the algorithms used. If Mathematica is using a sparse representation
then any algorithm will be at least O(d^2). I know another system
that uses a uses a dense representation for univariate polynomials,
with Karatsuba and FFT multiplication. These methods are an order of
magnitude faster if your polynomials are dense.

From: dimitris on 8 Jan 2007 04:56
Don't judge Mathematica for a specific performance. It is the overal
that makes her better for other CAS. For example compare the obtained
results by Symbolic Integration of Definite Integrals and you will be
quite impressed about its skills.
Anyway, it just happens some CAS to be better on one task, some on
another.

To tell you the truth I believed (and I still believe somehow!)
Mathematica can achieve better performance here contrary to my
findings...
May be someone will suggest a better way!

In[64]:=
Plus @@ Table[Random[Integer, {0, 1000}]*x^i, {i, 0, 1000}]
Plus @@ Table[Random[Integer, {0, 1000}]*x^i, {i, 0, 1000}]

In[69]:=
Timing[Collect[%*%%, x]][[1]]
Out[69]=
2.3279999999999745*Second

(CPU 2.8 GHz)





dmharvey(a)math.harvard.edu wrote:
> Hi,
>
> I'm trying to figure out how fast mathematica can multiply polynomials
> with integer coefficients. I don't know mathematica well at all, but I
> had a friend write me a mathematica program to test this. It look like
> on a regular desktop machine it can multiply e.g. degree 1000
> polynomials with coefficients in the range 0 <= x <= 1000 in about 1.3
> seconds.
>
> This is ludicrously slow compared to some other computer algebra
> systems, which can do this multiplication in about 0.0003
> seconds. I can't believe mathematica is in the order of 10000 times
> slower for this simple task. I think perhaps we are doing something
> wrong. Can anyone suggest a way of coaxing mathematica into doing this
> kind of arithmetic at a comparable pace?
>
> Many thanks
>
> David

From: mcmcclure on 8 Jan 2007 04:59
On Jan 6, 11:28 pm, dmhar...(a)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

From: Carl Woll on 8 Jan 2007 05:02
dmharvey(a)math.harvard.edu wrote:

>Hi,
>
>I'm trying to figure out how fast mathematica can multiply polynomials
>with integer coefficients. I don't know mathematica well at all, but I
>had a friend write me a mathematica program to test this. It look like
>on a regular desktop machine it can multiply e.g. degree 1000
>polynomials with coefficients in the range 0 <= x <= 1000 in about 1.3
>seconds.
>
>This is ludicrously slow compared to some other computer algebra
>systems, which can do this multiplication in about 0.0003
>seconds. I can't believe mathematica is in the order of 10000 times
>slower for this simple task. I think perhaps we are doing something
>wrong. Can anyone suggest a way of coaxing mathematica into doing this
>kind of arithmetic at a comparable pace?
>
>Many thanks
>
>David
>
>
I think the problem is with the representation of a polynomial. Assuming
we are dealing with univariate polynomials, we can represent the
polynomial as a list of coefficients:

c = {900, 801, etc}

or as a polynomial with explicit multiplications and additions:

p = 900 + 801*x + etc.

If we work with lists, we can use ListConvolve to do the multiplication.
If we work with polynomials, we will probably use Expand. Here is an
example multiplying two polynomials in both ways. Here are the coefficients:

In[1]:=
c1 = Table[Random[Integer, {0, 1000}], {1001}];
c2 = Table[Random[Integer, {0, 1000}], {1001}];

Here are the equivalent polynomials:

In[3]:=
p1 = x^Range[0, 1000] . c1;
p2 = x^Range[0, 1000] . c2;

Here we time multiplication using ListConvolve:

In[5]:=
c = ListConvolve[c1, c2, {1, -1}, 0]; // Timing
Out[5]=
{0. Second, Null}

Here we time multiplication using Expand:

In[6]:=
p = Expand[p1 p2]; // Timing
Out[6]=
{2.25 Second, Null}

Finally, we check that the two approaches yield the same result:

In[7]:=
c === CoefficientList[p, x]
Out[7]=
True

So, if one is interested in multiplying large, dense univariate
polynomials in Mathematica, the fastest approach is to use ListConvolve.

Carl Woll
Wolfram Research

 |  Next  |  Last
Pages: 1 2 3
Prev: Minimization with constraint expresses as CDF[] >=
Next: pursuit curve (differential equations)