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
- Effect of Simplify on numeric vs symbolic