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

```

• Prev by Date: Re: Re: enumerating list items
• Next by Date: Re: Effect of Simplify on numeric vs symbolic
• Previous by thread: Re: Effect of Simplify on numeric vs symbolic
• Next by thread: Re: Effect of Simplify on numeric vs symbolic