Re: Effect of Simplify on numeric vs symbolic

*To*: mathgroup at smc.vnet.net*Subject*: [mg56066] Re: Effect of Simplify on numeric vs symbolic*From*: carlos at colorado.edu*Date*: Thu, 14 Apr 2005 08:56:28 -0400 (EDT)*References*: <200504120926.FAA27663@smc.vnet.net><d3ib5q$9pp$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Daniel Lichtblau wrote: > carlos at colorado.edu wrote: > > In my previous example of FEM symbolic vs numeric speed all > > computations were with numbers. No variables were involved. > > The difference (minutes vs seconds) due largely due to Simplify. > > > > Here is a simpler example that illustrates the point, also taken from > > the same course. LineGaussRuleInfo returns weights and abcissae of 1D > > Gauss-Legendre quadrature rules of 1 to 5 points. Argument numer asks > > for exact information if False; if True it returns N[information]. > > All computations involve nunbers only. > > > > Results of calls (at end of post) on a Mac laptop: > > > > numer rule n Eval time Simplify time > > True 4 50 0.00 sec 0.00 sec > > False 4 50 0.00 sec 78.01 sec (* Note: FullSimplify needed *) > > False 4 50 0.00 sec 0.00 sec (* found result in cache *) > > > > LineGaussRuleInfo[{rule_,numer_},point_]:= Module[ > > {g2={-1,1}/Sqrt[3],w3={5/9,8/9,5/9}, > > g3={-Sqrt[3/5],0,Sqrt[3/5]}, > > w4={(1/2)-Sqrt[5/6]/6, (1/2)+Sqrt[5/6]/6, > > (1/2)+Sqrt[5/6]/6, (1/2)-Sqrt[5/6]/6}, > > g4={-Sqrt[(3+2*Sqrt[6/5])/7],-Sqrt[(3-2*Sqrt[6/5])/7], > > Sqrt[(3-2*Sqrt[6/5])/7], Sqrt[(3+2*Sqrt[6/5])/7]}, > > g5={-Sqrt[5+2*Sqrt[10/7]],-Sqrt[5-2*Sqrt[10/7]],0, > > Sqrt[5-2*Sqrt[10/7]], Sqrt[5+2*Sqrt[10/7]]}/3, > > w5={322-13*Sqrt[70],322+13*Sqrt[70],512, > > 322+13*Sqrt[70],322-13*Sqrt[70]}/900, > > i=point,p=rule,info={{Null,Null},0}}, > > If [p==1, info={0,2}]; > > If [p==2, info={g2[[i]],1}]; > > If [p==3, info={g3[[i]],w3[[i]]}]; > > If [p==4, info={g4[[i]],w4[[i]]}]; > > If [p==5, info={g5[[i]],w5[[i]]}]; > > If [numer, Return[N[info]], Return[info] ]; > > ]; > > > > PerverseExpression[rule_,n_,numer_]:=Module[{xw,tEval,tSymb,x}, > > xw=Table[LineGaussRuleInfo[{rule,numer},i],{i,1,rule}]; > > {tEval,x}=Timing[Product[(i+2)*xw[[i,1]]^n,{i,1,rule}]]; > > {tSymp,x}=Timing[FullSimplify[x]]; > > Return[{tEval,tSymp,x}]]; > > > > Print[PerverseExpression[4,50,True ]]; > > Print[PerverseExpression[4,50,False]]; > > Print[PerverseExpression[4,50,False]]; (* Cached *) > > > I have run this example on several Linux versions (3.0, 4.2, present, > and future). It never seems to take more than about 0.1 second for the > first invocation of PerverseExpression[4,50,False]. So either you have > found a strange platform dependency or you ran something other than what > you sent. > > The general question remains as to whether or why something of this sort > (involving products of possibly nested radicals) might be slow to > simplify. I'll just say that symbolic simplification can employ methods > that become arbitrarily bad for a given type of problem. In this case > there is a way out. I'll start with the code. > > First I rewrote so it would be more to my liking (maybe I should mention > that I don't much like Fortran. In any language.) This is a bit awkward > in that it uses globals for g and w, but I saw no point to doing > otherwise as they used in a way that is essentially static. In > production code one might do as I did but put them in a specialized context. > > g = {{0}, {-1,1}/Sqrt[3], Sqrt[3/5]*{-1,0,1}, > {-Sqrt[(3+2*Sqrt[6/5])/7],-Sqrt[(3-2*Sqrt[6/5])/7], > Sqrt[(3-2*Sqrt[6/5])/7], Sqrt[(3+2*Sqrt[6/5])/7]}, > {-Sqrt[5+2*Sqrt[10/7]],-Sqrt[5-2*Sqrt[10/7]],0, > Sqrt[5-2*Sqrt[10/7]], Sqrt[5+2*Sqrt[10/7]]}/3}; > > w = {{2}, {1,1}, {5/9,8/9,5/9}, > {(1/2)-Sqrt[5/6]/6, (1/2)+Sqrt[5/6]/6, > (1/2)+Sqrt[5/6]/6, (1/2)-Sqrt[5/6]/6}, > {322-13*Sqrt[70],322+13*Sqrt[70],512, > 322+13*Sqrt[70],322-13*Sqrt[70]}/900}; > > LineGaussRuleInfo[p_,i_,numer_:True] := > If [numer,N[#],#]& [{g[[p,i]],w[[p,i]]}] > > PerverseExpression[rule_,n_,numer_:True] := Module[{xw, x}, > xw = Table[LineGaussRuleInfo[rule,i,numer], {i,rule}]; > x = Product[(i+2)*xw[[i,1]]^n, {i,rule}]; > Timing[FullSimplify[x]] > ] > > This alone does not buy us any speed; I simply prefer the code in this > form for further work. The next undocumented tactic will put the > algebraics we use into a common number field. This will often make the > speed of manipulation considerably better than might otherwise be the case. > > g = {{0}, {-1,1}/Sqrt[3], Sqrt[3/5]*{-1,0,1}, > Algebraics`Private`NFToCommonField[ > {-Sqrt[(3+2*Sqrt[6/5])/7],-Sqrt[(3-2*Sqrt[6/5])/7], > Sqrt[(3-2*Sqrt[6/5])/7], Sqrt[(3+2*Sqrt[6/5])/7]}], > Algebraics`Private`NFToCommonField[ > {-Sqrt[5+2*Sqrt[10/7]],-Sqrt[5-2*Sqrt[10/7]],0, > Sqrt[5-2*Sqrt[10/7]], Sqrt[5+2*Sqrt[10/7]]}/3]}; > > If we now do the rest of the computations, in a fresh kernel session, > say, we find that the exact case is about as fast as the numeric and > still gives > 51688655113813386391457928 / > 31947156789289937013270310127837514166970738216377867502160\ > 370349884033203125 > (about 1.62*10^(-51)). > > This simply illustrates the age-old lesson that a specialized approach > will often beat a general one, if it is not obvious in the general case > what specialized route(s) to take and in what order. > > > Daniel Lichtblau > Wolfram Research That is a truly impressive speedup! Here is a tougher test. Can you run this script on the Unix version? xnum=((6-4*Sqrt[2])*Log[3-2*Sqrt[2]]+(3-2*Sqrt[2])* Log[17-12*Sqrt[2]]+32-24*Sqrt[2]); xden=(48*Sqrt[2]-72)*(Log[Sqrt[2]+1]+Sqrt[2])/3; x=xnum/xden; Print["neo, you are the one:",N[x,300]//InputForm]; xtab=Expand[{x,x^2,x^4,x^8,x^16,x^32}]; n=Length[xtab]; Print[Table[LeafCount[xtab[[i]]],{i,n}]]; Print[Table[Timing[FullSimplify[xtab[[i]]]],{i,n}]]; The simplified x should be 1.

**References**:**Effect of Simplify on numeric vs symbolic***From:*carlos@colorado.edu