Re: Re: Multiplying large polynomials
- To: mathgroup at smc.vnet.net
- Subject: [mg14763] Re: [mg14744] Re: Multiplying large polynomials
- From: Carl Woll <carlw at u.washington.edu>
- Date: Sat, 14 Nov 1998 03:07:55 -0500
- Organization: Physics Department, U of Washington
- References: <7257a7$88m@smc.vnet.net> <199811120717.CAA25067@smc.vnet.net.>
- Sender: owner-wri-mathgroup at wolfram.com
Hi Allan,
There's a mistake in your large polynomial description
> poly1 =
> Table[Random[Integer, {1, 50}]h^n, {n, 0, 100}];
>
I think you meant Sum instead of Table. However, this doesn't change the
order of the Timings, so that Tom's method is still the fastest. As you
mentioned, this is due to the length of time Series takes to convert a
simple polynomial into a SeriesData object. Consider the following code
fragment:
In[82]:=
Timing[Do[p1=poly1+O[h]^51,{10}]]
Timing[Do[p2=SeriesData[h,0,CoefficientList[poly1,h],0,51,1],{10}]]
p1===p2
Out[82]=
{9.16 Second,Null}
Out[83]=
{0.11 Second,Null}
Out[84]=
True
where I compare the usual way of converting an expression into a
SeriesData object with just creating the SeriesData object by hand
using CoefficientList. As you can see, the second method is 2 orders of
magnitude faster. I think this is due to the fact that Series works by
really doing a Taylor expansion. That is, Series may actually take 50
derivatives of poly1 to determine the SeriesData object.
Based on the above, the fastest approach is to create the SeriesData
objects by hand, and then multiply the Series expressions. Moreover, if
one will multiply the same SeriesData object more than once, it won't
take long before the approach of converting to Series first wins out,
since multiplying SeriesData objects is very quick. Witness the
following code fragment:
In[90]:=
poly1=Sum[Random[]h^n,{n,0,100}];
poly2=Sum[Random[]h^n,{n,0,100}];
Timing[Do[spoly1=poly1+O[h]^51,{10}]]
Timing[Do[spoly2=poly2+O[h]^51,{10}]] Timing[Do[spoly1
spoly2//Normal,{10}]] Timing[Do[Series[poly1
poly2,{h,0,50}]//Normal,{10}]] Timing[Do[Expand[poly1
poly2]/.h^n_?(#>50&)->0,{10}]]
Out[90]=
{9.25 Second,Null}
Out[91]=
{9.38 Second,Null}
Out[92]=
{0.6 Second,Null}
Out[93]=
{18.9 Second,Null}
Out[94]=
{14. Second,Null}
where multiplying 2 SeriesData objects takes 0.6 seconds, compared to 14
seconds for multiplying out 2 regular polynomial objects.
Carl Woll
Dept of Physics
U of Washington
Allan Hayes wrote:
> Several postings have used Series to do get the answer. In the timings
> below the use of replacement after multiplication (as in Thomas Bell's
> original posting) gives the quickest computation and it appears that
> the difference is because evaluating Series takes a long time (are
> there any memory usage compensations when using Series?)
>
> poly1 = a h^2 + b;
> poly2 = d h + e;
>
> Carl Woll and Rolf Mertig
> Do[(poly1 + O[h]^3 )(poly2 + O[h]^3) // Normal, {100}]//Timing
>
> {0.71 Second, Null}
>
> Ted Ersek
> Do[Series[poly1*poly2, {h, 0, 2}] // Normal, {100}] // Timing
>
> {0.55 Second, Null}
>
> Thomas Bell (Extended)
> Do[Expand[poly1*poly2] /. h^n_?(# > 2 &) -> 0, {100}] // Timing
>
> {0.16 Second, Null}
>
> ** And for larger polynomials**
>
> poly1 =
> Table[Random[Integer, {1, 50}]h^n, {n, 0, 100}];
>
> poly2 =
> Table[Random[Integer, {1, 50}]h^n, {n, 0, 100}];
>
> Timing[Do[(poly1 + O[h]^51)(poly2 + O[h]^51) // Normal, {10}]]
>
> {6.59 Second, Null}
>
> Do[Series[poly1*poly2, {h, 0, 50}] // Normal, {10}] // Timing
>
> {3.51 Second, Null}
>
> Do[Expand[poly1*poly2] /. h^n_?(# > 50 &) -> 0, {10}] // Timing
>
> {0.44 Second, Null}
>
> ** Separating out the expansions in the first computation shows that
> most of the time is taken up with the expansions **
>
> Do[(s1 = poly1 + O[h]^51; s2 = poly2 + O[h]^51;), {10}] // Timing
>
> {6.15 Second, Null}
>
> Timing[Do[s1 s2 // Normal, {10}]]
>
> {0.5 Second, Null}
>
> Allan
>
> ---------------------
> Allan Hayes
> Mathematica Training and Consulting
> www.haystack.demon.co.uk
> hay at haystack.demon.co.uk
> Voice: +44 (0)116 271 4198
> Fax: +44 (0)870 164 0565
>
> *******************************************************
>
> Thomas Bell wrote in message <7257a7$88m at smc.vnet.net>...
> >I'm trying to multiply two huge polynomials, and memory is a major
> >concern. I want to truncate the resulting polynomial to a specified
> >power (N) in one of the variables (h), and I was wondering if it was
> >possible to tell Mathematica to not bother multiplying two terms if the
> >resulting power of h was greater than N. This is, of course, in the
> >hope that this "automatic truncation" would save time and memory. For
> >example, if
> >
> >poly1 = a h^2 + b;
> >poly2 = d h + e;
> >N = 2;
> >
> >then I would like to result to be
> >
> >result = a e h^2 + b d h + b e
> >
> >Instead, I have to write
> >
> >result = Expand[poly1 poly2]/.h^3 -> 0;
> >
> >which forces Mathematica to create the enormous product before
> >truncating. Please cc to tombell at stanford.edu, and thanks in advance
> >for any suggestions.
- References:
- Re: Multiplying large polynomials
- From: "Allan Hayes" <hay@haystack.demon.co.uk>
- Re: Multiplying large polynomials