Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Effect of Simplify on numeric vs symbolic

• To: mathgroup at smc.vnet.net
• Subject: [mg56009] Re: [mg55971] Effect of Simplify on numeric vs symbolic
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Wed, 13 Apr 2005 01:10:51 -0400 (EDT)
• References: <200504120926.FAA27663@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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

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