MathGroup Archive 2011

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

Search the Archive

Re: decoding inbuilt function

  • To: mathgroup at smc.vnet.net
  • Subject: [mg121096] Re: decoding inbuilt function
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Sat, 27 Aug 2011 08:16:57 -0400 (EDT)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • References: <201108221003.GAA22469@smc.vnet.net> <4592974.8304.1314168104259.JavaMail.root@m06> <201108260925.FAA04591@smc.vnet.net>

On 08/26/2011 04:25 AM, student wrote:
> hi,
> i was trying to get the cas logic in  computing limits
> i never meant to decode a proprietary software illegally (just a try
> to understand the logic behind)
> so i really need to modify my question
> WHAT IS THE CAS LOGIC BEHIND COMPUTING LIMITS IN MATHEMATICA
>
> i really thank everybody who responded in a positive way to help me
> especially simon sir for the help rendered and rest of them really
> guided me in a right way so i thank them all
> anyway it is really clear that the logic is gruntz algorithm (which
> looks really confusing)
> so can u people please help me in this case
>
> thanking all

Simon Tyler's response was on track. The actual situation is quite 
complicated (which was the main reason I was loathe to get into this). I 
still won't try to outline the code in any detail, but I will explain 
several of the considerations that went into it.

(1) One often can use a basic power series expansion.

(2) The Gruntz algorithm is quite powerful, in its area of 
applicability. But...
   (i) It does not really know how to handle oscillatory functions.
   (ii) It does not handle non-numeric parameters, even if we have some 
ranges in which they live e.g. from assumptions.
   (iii) It does not handle things with jump discontinuities e.g. from 
branch cut crossings.
   (iv) It does not handle (most) special functions directly. Some 
extensions of the algorithm understand certain such functions, but I do 
not think there is any general way to apply it universally.
   (v) It does not handle complex valued functions. We try, when 
possible, to separate into real and imaginary parts in a way that uses 
functions it will understand. ComplexExpand gets utilized here.

(3) The handling of special functions involves attempts to change them 
into elementary functions, possibly by conversion to series (at 
infinity, when applicable). Mathematica's Series code attempts to do 
this sort of conversion in part because it is understood to be useful 
for Limit.

(4) The handling of branch cuts gets tricky. We try to deduce the 
direction of approach, taking into account parameters and assumptions 
thereon (as well as interval bounds for oscillatory functions). We use a 
knowledge base of branch cut behavior for the elementary functions and a 
number of special functions. We have also some knowledge built into 
Series for handling these discontinuities via Floor, Arg, and the like. 
We do not claim this to be a particularly elegant way of handling the 
expansions, and it is not uniformly applied (Series takes this approach 
for special functions but not for elementary functions).

(5) It is not easy to make adequate use of assumptions on parameter 
values. One cannot apply Simplify every which way (many things would 
start to hang). We tend to use Refine[...,Assumptions->...] and hope for 
the best. But there will be situations where a needed inference is missed.

(6) There are other functions with jump discontinuities, such as 
UnitStep, Sign, and Floor. Handling these can be a nightmare. While I 
have forgotten what type of reptile we had to sacrifice to make that 
stuff (usually) work, I can say with assurance that it was big enough to 
leave scars.

The basic methodology to the code is to check whether the function is 
trivial to handle (e.g. a rational function), if not check whether we 
think we have functions with possible branch cuts or jumps for other 
reasons. If so then we then go though an elaborate "dance of recursion" 
as we drill down into the function (not pretty--it resembles the mating 
ritual of ostriches). At some point we try series expansions, and one of 
those will attempt the Gruntz algorithm. I will mention that in many 
respects the use of Gruntz' algorithm is amongst the "cleanest" parts of 
Limit. That's because it is really and truly algorithmic (although 
subject to limitations that rarely arise in practice), whereas much of 
the other handling via Series and branch cut detection involves a bag of 
tricks.

If all this fails, we try in a different way to deconstruct the 
functions and reattempt to take limits. There are also heuristic 
conversions by taking logs or exponentials (taking care one does not 
simply undo the other). There is even some ancient code that tries 
l'Hospital's rule. Again dicey, since that can lead in a roundabout way 
to the same problem in disguise (so it cannot be done repeatedly without 
extreme care).

This might give a very rough idea of what Limit will do. The reasons for 
not going into more detail have less to do with it being proprietary 
than with it being a thick forest I don't care to get lost in yet again.

Daniel Lichtblau
Wolfram Research




  • Prev by Date: Problem with NIntegrating a compiled function
  • Next by Date: Calling Mathematica from Java
  • Previous by thread: Re: decoding inbuilt function
  • Next by thread: Re: decoding inbuilt function