Re: Re: Re: Re: Significant slow-down with
- To: mathgroup at smc.vnet.net
- Subject: [mg95998] Re: [mg95962] Re: [mg95957] Re: [mg95913] Re: [mg95826] Significant slow-down with
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 31 Jan 2009 06:45:21 -0500 (EST)
- References: <200901310611.BAA28338@smc.vnet.net>
This is the first really impressive demonstration of the usefulness of parallel processing in Mathematica. I think it ought to be included in the documentation, which badly needs such examples. In particular, it provides a convincing answer the question posted here: http://forums.wolfram.com/mathgroup/archive/2008/Nov/msg00444.html Those still skeptical should demonstrate how they would deal with this particular problem using C, Fortran or even Ocaml ;-) Andrzej Kozlowski On 31 Jan 2009, at 07:11, Adam Strzebonski wrote: > 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 >>> >>> >> >
- References:
- Re: Re: Re: Significant slow-down with
- From: Adam Strzebonski <adams@wolfram.com>
- Re: Re: Re: Significant slow-down with