MathGroup Archive 2009

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

Search the Archive

Re: Re: Re: Significant slow-down with

  • To: mathgroup at smc.vnet.net
  • Subject: [mg95962] Re: [mg95957] Re: [mg95913] Re: [mg95826] Significant slow-down with
  • From: Adam Strzebonski <adams at wolfram.com>
  • Date: Sat, 31 Jan 2009 01:11:42 -0500 (EST)

One more remark. On machines with multiple cores, one can
use ParallelTry to run both methods in parallel and get
the result from whichever method finishes faster.
This will still work on machines with one core, except that
the RootReduce calls for which the automatic method selection
works well will be twice slower.

LaunchKernels[2]
{KernelObject[1, "local"], KernelObject[2, "local"]}

PRootReduce[a_] :=
  ParallelTry[RootReduce[a, Method->#]&, {"Recursive", "NumberField"}]

AbsoluteTiming[PRootReduce[x] // Short]

{1.485447, Root[-2769706384-<<1>>+324 <<2>>^4&, 2]}

AbsoluteTiming[PRootReduce[e] // Short]

{0.849569, Root[<<1>>&, 1]}

Best regards,

Adam Strzebonski
Wolfram Research

Adam Strzebonski wrote:
 > The difference can be arbitrarily large in either direction.
 > Here is an example where the "NumberField" method is faster
 > by a factor of 7700, and the automatic method selection does
 > pick the faster method.
 >
 > a=Root[#^3-#-1&, 1];
 > b=2^(1/6);
 > SeedRandom[1];
 > e=Sum[RandomInteger[{-100, 100}] a^i b^j, {i, 0, 2}, {j, 0, 5}];
 >
 > In[5]:= RootReduce[e, Method->"Recursive"]//Timing//InputForm
 >
 > Out[5]//InputForm=
 > {1506.076042, Root[50505808949809153821722941914635112509348143 +
 >     365741513511248529376047597425831003016630*#1 +
 >     1473003695813636128968413692365061482423*#1^2 -
 >     3359272977645340460068844677894763898*#1^3 -
 >     2268307929809600173042830013292805*#1^4 -
 >     341043359192920761513389626609458*#1^5 -
 > 376075465654830707036759067602*
 >      #1^6 + 4778789762834862609186205542*#1^7 + 
17180009746242542883294492*
 >      #1^8 - 158122155627340901637452*#1^9 - 551174348020538766903*#1^10 +
 >     5346473922554086776*#1^11 + 36128131851043581*#1^12 +
 >     68316117333306*#1^13 - 84751803045*#1^14 - 450805238*#1^15 -
 > 1710*#1^16 +
 >     1392*#1^17 + #1^18 & , 1, 0]}
 >
 > In[6]:= RootReduce[e]//Timing//InputForm
 >
 > Out[6]//InputForm=
 > {0.19397000000008335, Root[50505808949809153821722941914635112509348143 +
 >     365741513511248529376047597425831003016630*#1 +
 >     1473003695813636128968413692365061482423*#1^2 -
 >     3359272977645340460068844677894763898*#1^3 -
 >     2268307929809600173042830013292805*#1^4 -
 >     341043359192920761513389626609458*#1^5 -
 > 376075465654830707036759067602*
 >      #1^6 + 4778789762834862609186205542*#1^7 + 
17180009746242542883294492*
 >      #1^8 - 158122155627340901637452*#1^9 - 551174348020538766903*#1^10 +
 >     5346473922554086776*#1^11 + 36128131851043581*#1^12 +
 >     68316117333306*#1^13 - 84751803045*#1^14 - 450805238*#1^15 -
 > 1710*#1^16 +
 >     1392*#1^17 + #1^18 & , 1, 0]}
 >
 > This example is actually pretty close to the method crossover
 > in the current heuristic. If I change b to 2^(1/8) the method
 > automatically selected is "Recursive", even though "NumberField"
 > is much faster for that example too. Unfortunately I wasn't
 > able to find a better way to decide a priori which method will
 > be faster...
 >
 > Best regards,
 >
 > Adam Strzebonski
 > Wolfram Research
 >
 >
 > van der Burgt, Maarten wrote:
 >> The difference is enormous on my system (laptop Vista Centrino dual core
 >> 2.4GHz):
 >>
 >> Timing[RootReduce[x, Method -> "Recursive"]]
 >> {0.297, Root[-2769706384 - 370035819 #1^2 + 324 #1^4 &, 2]}
 >>
 >> Timing[RootReduce[x, Method -> "NumberField"]]
 >> {991.885, Root[-2769706384 - 370035819 #1^2 + 324 #1^4 &, 2]}
 >>
 >>
 >> Best regards,
 >>
 >> Maarten van der Burgt
 >>
 >> -----Original Message-----
 >> From: Adam Strzebonski [mailto:adams at wolfram.com]
 >> Sent: Thursday, 29 January, 2009 12:00
 >> To: mathgroup at smc.vnet.net
 >> Subject: [mg95913] Re: [mg95826] Significant slow-down with Mathematica
 >> 7 (vs 6).
 >>
 >> In Mathematica 7 RootReduce has a choice of two methods.
 >>
 >> Method->"Recursive" recursively performs algebraic number arithmetic,
 >> in a very similar way to what Mathematica 6 RootReduce was doing
 >>
 >> Method->"NumberField" first converts algebraic numbers in the input
 >> to AlgebraicNumber objects with the same generator and then performs
 >> the arithmetic within the algebraic number field.
 >>
 >> For each of the two methods there are examples where the method
 >> is significantly (by more than a factor of 1000) faster than
 >> the other one. With the default setting Method->Automatic, RootReduce
 >> attempts to heuristically pick the faster method. Unfortunately,
 >> there is no way to tell a priori which method will be faster and
 >> for some examples the heuristic makes the wrong choice.
 >>
 >> For your example the automatic method selection picks the "NumberField"
 >> method, but the "Recursive" method is much faster.
 >>
 >> In[3]:= RootReduce[x, Method->"Recursive"]//Timing
 >>
 >>                                                  2         4
 >> Out[3]= {1.36009, Root[-2769706384 - 370035819 #1  + 324 #1  & , 2]}
 >>
 >> For comparison, Mathematica 6 run on the same machine gives
 >>
 >> In[3]:= RootReduce[x]//Timing
 >>
 >>                                                  2         4
 >> Out[3]= {2.85218, Root[-2769706384 - 370035819 #1  + 324 #1  & , 2]}
 >>
 >> so Mathematica 7, with the "Recursive" method is even somewhat faster
 >> than Mathematica 6.
 >>
 >> If you see that Mathematica 7 RootReduce is slower than Mathematica 6
 >> on a significant portion of examples that appear in your calculations,
 >> you should probably use SetOptions[RootReduce, Method->"Recursive"].
 >>
 >> I would be grateful if you could send me a few more of the examples,
 >> so that I could use them to better tune the automatic method selection.
 >>
 >> Best Regards,
 >>
 >> Adam Strzebonski
 >> Wolfram Research
 >>
 >> Scott Morrison wrote:
 >>> I use RootReduce extremely heavily (subfactor/planar algebra
 >>> calculations). I've recently discovered that in many cases RootReduce
 >>> in Mathematica 7 runs significantly slower than in Mathematica 6. (Of
 >>
 >> course, I've
 >>> checked on the same machine.)
 >>>
 >>> As an example, try RootReduce[x] with
 >>>
 >>> x =
 >>> (Sqrt[(-1 + Sqrt[17])*(1 + Sqrt[17])]*
 >>>      Root[-2 - 3*#1^2 + #1^4 & , 2, 0]*
 >>>      Root[128 - 8055*#1^2 + 81*#1^4 & , 4, 0])/
 >>>    2 + (Sqrt[
 >>>       5 + Sqrt[17]]*(Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-32 - 5*#1^2 + #1^4 & , 2, 0]*
 >>>         Root[32768 - 78588*#1^2 + 81*#1^4 & , 4, 0] -
 >>>        2*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-16384 - 36144*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        Sqrt[2*(5 - Sqrt[17])]*Root[-2 - 3*#1^2 + #1^4 & , 2, 0]*
 >>>         Root[128 - 8055*#1^2 + 81*#1^4 & , 4, 0]))/
 >>>    2 + (Sqrt[
 >>>       5 + Sqrt[17]]*(4*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-32 - 5*#1^2 + #1^4 & , 2, 0]*
 >>>         Root[32768 - 78588*#1^2 + 81*#1^4 & , 4, 0] +
 >>>        4*Sqrt[2*(5 - Sqrt[17])]*Root[32 - 23*#1^2 + 4*#1^4 & , 1,
 >> 0]*
 >>>         Root[-8192 - 30645*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        9*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-16384 - 13347*#1^2 + 81*#1^4 & , 2, 0] -
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-16384 - 13347*#1^2 + 81*#1^4 & , 2, 0] +
 >>>        4*Sqrt[2*(5 - Sqrt[17])]*Root[-8 + 11*#1^2 + #1^4 & , 1, 0]*
 >>>         Root[8192 - 6300*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-1024 - 5499*#1^2 + 81*#1^4 & , 2, 0] -
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-1024 - 5499*#1^2 + 81*#1^4 & , 2, 0]))/
 >>>    8 + (Sqrt[
 >>>       5 + Sqrt[17]]*(38*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-4 + #1^2 + #1^4 & , 2, 0] +
 >>>        10*Sqrt[34*(5 - Sqrt[17])]*Root[-4 + #1^2 + #1^4 & , 2, 0] -
 >>>        12*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-16384 - 36144*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        6*Sqrt[2*(5 - Sqrt[17])]*Root[-8 + 11*#1^2 + #1^4 & , 1, 0]*
 >>>         Root[8192 - 6300*#1^2 + 81*#1^4 & , 1, 0] -
 >>>        9*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-4096 - 2736*#1^2 + 81*#1^4 & , 2, 0] +
 >>>        3*Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-4096 - 2736*#1^2 + 81*#1^4 & , 2, 0] +
 >>>        6*Sqrt[2*(5 - Sqrt[17])]*Root[-1 + 3*#1^2 + 2*#1^4 & , 2, 0]*
 >>>         Root[512 - 2556*#1^2 + 81*#1^4 & , 1, 0]))/
 >>>    12 + (Sqrt[
 >>>       5 + Sqrt[17]]*(Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-16 - 251*#1^2 + 4*#1^4 & , 1, 0] +
 >>>        2*Sqrt[2*(5 - Sqrt[17])]*Root[-1 + 3*#1^2 + 2*#1^4 & , 1, 0]*
 >>>         Root[512 - 2556*#1^2 + 81*#1^4 & , 4, 0]))/
 >>>    4 + (Sqrt[
 >>>       5 + Sqrt[17]]*(2*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-1 + 3*#1^2 + 2*#1^4 & , 1, 0]*
 >>>         Root[512 - 2556*#1^2 + 81*#1^4 & , 4, 0] -
 >>>        3*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-256 - 684*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-256 - 684*#1^2 + 81*#1^4 & , 1, 0]))/
 >>>    4 + (Sqrt[(-1 + Sqrt[17])*(1 + Sqrt[17])]*
 >>>      Root[-1 + 3*#1^2 + 2*#1^4 & , 1, 0]*
 >>>      Root[32 - 639*#1^2 + 81*#1^4 & , 1, 0])/
 >>>    2 + (Sqrt[
 >>>       5 + Sqrt[17]]*(2*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-8 + 11*#1^2 + #1^4 & , 1, 0]*
 >>>         Root[8192 - 6300*#1^2 + 81*#1^4 & , 1, 0] -
 >>>        3*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-4096 - 2736*#1^2 + 81*#1^4 & , 2, 0] +
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-4096 - 2736*#1^2 + 81*#1^4 & , 2, 0] +
 >>>        2*Sqrt[2*(5 - Sqrt[17])]*Root[-1 + 3*#1^2 + 2*#1^4 & , 1, 0]*
 >>>         Root[32 - 639*#1^2 + 81*#1^4 & , 1, 0]))/
 >>>    4 + (Sqrt[(-1 + Sqrt[17])*(1 + Sqrt[17])]*
 >>>      Root[2 - 7*#1^2 + 4*#1^4 & , 1, 0]*
 >>>      Root[-128 - 12573*#1^2 + 324*#1^4 & , 1, 0])/
 >>>    2 + (Sqrt[
 >>>       5 + Sqrt[17]]*(19*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-4 + #1^2 + #1^4 & , 2, 0] +
 >>>        5*Sqrt[34*(5 - Sqrt[17])]*Root[-4 + #1^2 + #1^4 & , 2, 0] +
 >>>        3*Sqrt[2*(5 - Sqrt[17])]*Root[32 - 23*#1^2 + 4*#1^4 & , 1,
 >> 0]*
 >>>         Root[-8192 - 30645*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        3*Sqrt[2*(5 - Sqrt[17])]*Root[2 - 7*#1^2 + 4*#1^4 & , 1, 0]*
 >>>         Root[-128 - 12573*#1^2 + 324*#1^4 & , 1, 0]))/
 >>>    6 + ((-1 + Sqrt[17])^(3/2)*Sqrt[1 + Sqrt[17]]*
 >>>      Root[-256 - 5499*#1^2 + 324*#1^4 & , 2, 0])/
 >>>    8 + (Sqrt[
 >>>       5 + Sqrt[17]]*(9*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-16384 - 13347*#1^2 + 81*#1^4 & , 2, 0] -
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-16384 - 13347*#1^2 + 81*#1^4 & , 2, 0] +
 >>>        4*Sqrt[2*(5 - Sqrt[17])]*Root[-8 + 11*#1^2 + #1^4 & , 1, 0]*
 >>>         Root[8192 - 6300*#1^2 + 81*#1^4 & , 1, 0] -
 >>>        Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-256 - 5499*#1^2 + 324*#1^4 & , 2, 0] +
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-256 - 5499*#1^2 + 324*#1^4 & , 2, 0]))/
 >>>    8 + (Sqrt[
 >>>       5 + Sqrt[17]]*(4*Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-2 - 3*#1^2 + #1^4 & , 2, 0]*
 >>>         Root[128 - 8055*#1^2 + 81*#1^4 & , 4, 0] +
 >>>        Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-1024 - 5499*#1^2 + 81*#1^4 & , 2, 0] -
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-1024 - 5499*#1^2 + 81*#1^4 & , 2, 0] +
 >>>        4*Sqrt[2*(5 - Sqrt[17])]*Root[-1 + 3*#1^2 + 2*#1^4 & , 2, 0]*
 >>>         Root[512 - 2556*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        4*Sqrt[2*(5 - Sqrt[17])]*Root[-1 + 3*#1^2 + 2*#1^4 & , 1, 0]*
 >>>         Root[32 - 639*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        4*Sqrt[2*(5 - Sqrt[17])]*Root[2 - 7*#1^2 + 4*#1^4 & , 1, 0]*
 >>>         Root[-128 - 12573*#1^2 + 324*#1^4 & , 1, 0] -
 >>>        Sqrt[2*(5 - Sqrt[17])]*
 >>>         Root[-256 - 5499*#1^2 + 324*#1^4 & , 2, 0] +
 >>>        Sqrt[34*(5 - Sqrt[17])]*
 >>>         Root[-256 - 5499*#1^2 + 324*#1^4 & , 2, 0]))/
 >>>    8 + (Sqrt[(1 + Sqrt[17])/
 >>>        2]*(4*Sqrt[2*(-1 + Sqrt[17])]*
 >>>         Root[-2 - 3*#1^2 + #1^4 & , 2, 0]*
 >>>         Root[128 - 8055*#1^2 + 81*#1^4 & , 4, 0] +
 >>>        4*Sqrt[2*(-1 + Sqrt[17])]*Root[-1 + 3*#1^2 + 2*#1^4 & , 1,
 >> 0]*
 >>>         Root[32 - 639*#1^2 + 81*#1^4 & , 1, 0] +
 >>>        4*Sqrt[2*(-1 + Sqrt[17])]*Root[-1 + 3*#1^2 + 2*#1^4 & , 2,
 >> 0]*
 >>>         Root[32 - 639*#1^2 + 81*#1^4 & , 4, 0] +
 >>>        4*Sqrt[2*(-1 + Sqrt[17])]*Root[2 - 7*#1^2 + 4*#1^4 & , 1, 0]*
 >>>         Root[-128 - 12573*#1^2 + 324*#1^4 & , 1, 0] -
 >>>        Sqrt[2*(-1 + Sqrt[17])]*
 >>>         Root[-256 - 5499*#1^2 + 324*#1^4 & , 2, 0] +
 >>>        Sqrt[34*(-1 + Sqrt[17])]*
 >>>         Root[-256 - 5499*#1^2 + 324*#1^4 & , 2, 0]))/8;
 >>>
 >>> this runs in <2s in Mathematica 6 on my machine, and >30s in
 >> Mathematica7.
 >>> I have other examples where the difference is even worse.
 >>>
 >>> Thanks,
 >>> Scott Morrison
 >>
 >>
 >


  • Prev by Date: Re: Re: Simplifying and Rearranging Expressions
  • Next by Date: Re: Re: Simplifying and Rearranging Expressions
  • Previous by thread: Re: Can I Mapthis code?
  • Next by thread: Re: Re: Re: Re: Significant slow-down with