Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2009

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

Search the Archive

Re: Re: Significant slow-down with Mathematica

  • To: mathgroup at smc.vnet.net
  • Subject: [mg95957] Re: [mg95913] Re: [mg95826] Significant slow-down with Mathematica
  • From: Adam Strzebonski <adams at wolfram.com>
  • Date: Fri, 30 Jan 2009 05:48:01 -0500 (EST)
  • References: <200901291059.FAA18289@smc.vnet.net> <A4E4DA09141B9D419606C6D67A4078530915CE@BEL1EXCLV01.adcorp.kla-tencor.com>
  • Reply-to: adams at wolfram.com

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: Simplifying and Rearranging Expressions
  • Next by Date: MCMC in Mathematica
  • Previous by thread: Re: Re: Significant slow-down with Mathematica 7 (vs 6).
  • Next by thread: Re: Re: Re: Significant slow-down with