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

MathGroup Archive 2009

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

Search the Archive

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



  • Prev by Date: Re: Re: ListCurvePathPlot
  • Next by Date: Re: Can I Map[] this code?
  • Previous by thread: Re: Re: Re: Significant slow-down with
  • Next by thread: Lower Bound on Parameters in NonlinearFit, Mathematica 5.2