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>