description of Mathematica's Limit calculations

In case someone wishes to revise Maxima's limit program, this
information may be quite useful, especially with regard to when
Gruntz's algorithm does not work.
(This is from the mathematica newsgroup, as you can see from
the heading.)

There are a few areas in which Mathematica has forged ahead with
additional efforts, where additional work in Maxima's code base
might bring Maxima up to the same level.   I think Limit
is one of the areas.  Other areas include numerical integration,
symbolic integration, "Reduce".  That is not to say that Maxima does the 
same as Mathematica everywhere else, just that the technology for these 
commands strikes me as more interesting and useful than (say) the latest 
display hacks.  Arguably, Mathematica's matching program is more 
advanced (certainly different), but I already have Lisp code to do that, 
but it is tangled up in evaluation strategies.

Anyway, here's the description of Limit...


-------- Original Message --------
Subject: Re: decoding inbuilt function
Date: Sat, 27 Aug 2011 12:18:44 +0000 (UTC)
From: Daniel Lichtblau <danl at wolfram.com>
Organization: Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Newsgroups: comp.soft-sys.math.mathematica
References: <201108221003.GAA22469 at smc.vnet.net> 
<4592974.8304.1314168104259.JavaMail.root at m06> 
<201108260925.FAA04591 at 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