Re: Slow ReIm
- To: mathgroup at smc.vnet.net
- Subject: [mg3412] Re: Slow ReIm
- From: villegas (Robert Villegas)
- Date: Wed, 6 Mar 1996 01:44:52 -0500
- Organization: Wolfram Research, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
In article <4h13tr$rr4 at dragonfly.wolfram.com> Donald Darling <ddarling at math.uci.edu> writes: > Can someone tell me why, after I load the package ReIm and declare the > variables z and u real, it takes over 15 minutes to evaluate > Re[(1- I u z)/(1-2 I u z - z^2)] ? > > Thanks ... Don Darling. Algebra`ReIm` contains a lot of recursive expansions such as Re[x_ y_] := Re[x] Re[y] - Im[x] Im[y] Im[x_ y_] := Re[x] Im[y] + Im[x] Re[y] which cause rapid growth in the number of Re and Im expressions occurring in intermediate steps of the calculation. Of course, at the same time, the arguments of Re and Im are rapidly becoming simpler as the identities reduce them eventually to atoms like 'z', so although this consumes a nontrivial amount of time, it is not most of the problem. What is deadly is the following two rules near the top of ReIm.m: realQ[x_] /; !NumberQ[x] := Im[x] == 0 Re[x_] := x /; realQ[x] With these in effect, every single Re[expr] that is ever generated also evaluates Im[expr], which is a whole evaluation chain itself that will create lots of Re's and Im's, causing more Im checks, ad infinitum. Since Im[expr] will almost always evaluate to some symbolic expression that is not zero, a vast amount of work is wasted. It is easy to work around this: just eliminate those two rules from the package. When I did this on a fairly slow workstation, I got an answer back in 24 seconds. In[4]:= Re[(1- I u z)/(1-2 I u z - z^2)] /. {Re[z_] :> z, Im[z_] :> 0} 2 2 2 2 u z 1 - z Out[4]= ------------------- + ------------------- 2 2 2 2 2 2 2 2 4 u z + (1 - z ) 4 u z + (1 - z ) The answer is the same what ComplexExpand gives, though, which returns the answer in just a couple seconds: In[1]:= ComplexExpand[Re[(1- I u z)/(1-2 I u z - z^2)]] 2 2 2 2 u z 1 - z Out[1]= ------------------- + ------------------- 2 2 2 2 2 2 2 2 4 u z + (1 - z ) 4 u z + (1 - z ) ComplexExpand is usually far superior. As an exercise in using Trace, you can see just how many calls to realQ are occurring in this evaluation. Note that realQ is a private function in the package, so when we refer to it we have to use its context Algebra`ReIm`Private`. In[10]:= <<Algebra`ReIm` Here is a trace of all calls to Algebra`ReIm`Private`realQ: In[11]:= traceResult = Trace[Re[(1- I u z)/(1-2 I u z - z^2)], Algebra`ReIm`Private`realQ]; There are over eight thousand of them: In[12]:= realQCount = Count[traceResult, _Algebra`ReIm`Private`realQ, -1] Out[12]= 8159 Here is a breakdown by argument and number of times called: In[13]:= realQArguments = Cases[traceResult, Literal[Algebra`ReIm`Private`realQ[x_]] :> HoldForm[x], -1]; In[14]:= realQFreqs = Sort[Frequencies[realQArguments], Last[#1] >= Last[#2]& ] 2 Out[14]= {{z, 4474}, {u, 1914}, {u z, 634}, {z , 634}, {-2 I u z, 149}, 2 2 1 > {-z , 149}, {1 - 2 I u z - z , 149}, {----------------, 37}, 2 1 - 2 I u z - z z u z -I u z > {----------------, 12}, {----------------, 4}, {----------------, 1}, 2 2 2 1 - 2 I u z - z 1 - 2 I u z - z 1 - 2 I u z - z 1 - I u z 1 I u z > {----------------, 1}, {---------------- - ----------------, 1}} 2 2 2 1 - 2 I u z - z 1 - 2 I u z - z 1 - 2 I u z - z Robby Villegas ==== [MESSAGE SEPARATOR] ====