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] ====