Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Multiplying large polynomials

• To: mathgroup at smc.vnet.net
• Subject: [mg14744] Re: Multiplying large polynomials
• From: "Allan Hayes" <hay at haystack.demon.co.uk>
• Date: Thu, 12 Nov 1998 02:17:43 -0500
• References: <7257a7$88m@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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.
>
>

• Follow-Ups:
  • Re: Re: Multiplying large polynomials
    • From: Carl Woll <carlw@u.washington.edu>