What are the algorithms for symbolic definite integration? Apart from computing the antiderivative first.

What are the basic ideas behind such algorithms?

As far as I got it, the main idea behind symbolic indefinite integration is that we actually know what kind of terms should be in the answer. And it is easy to believe in this, since it is enough to think what kind of terms are produced during differentiation.

But for definite integrals it seems that the answer could be virtually any combination of known functions and constants.

I'm aware of experimental methods involving high-precision numerical integration and then using things like inverse symbolic calculator. But that's not what I'm looking for.


What I have found out by now.

The primary method for definite integration is based on the fundamental theorem of calculus. Thus it relies on algorithms for indefinite integration, though it's not as simple since one also have to study singularities between the boundaries.

The other one is based on representing the integrand in terms of Meijer's g-functions and integrating them.

Now turning to something more interesting algrithms. There is a method called "creative telescoping", which is much like "differentiating under the integral sign" method.

That is if the integral is parametrized with say $w$ one can try to find recurrence relations for that integral with respect to $w$. If we are lucky we can solve them to get the value of the integral.

These recurrence relations may be differential or difference equations or a mix of them.

The case of $w$ being continuous:

$$I(w) = \int_a^b f(x,w) \, dx$$

We want to find an annihilator operator for $f(x,w)\;$ ($\bullet$ denotes operator application $T[f]$):

$$ T \bullet f = 0$$

which consists of two parts:

$$T = P(w, D_w ) + D_x Q(x, w, D_x , D_w),$$

$D$ is the differentiation operator. The operator $P$ is called the principal part, and $Q$ is called the delta part. In that manner:

$$ \int_a^b T(x,w,D_x, D_f) \bullet f \, dx = 0 $$

$$P(w, D_w) \bullet I(w) + \left[ Q(x, w, D_x, D_w) \bullet f(x,w) \right] \Bigg|_a^b = 0 $$

If someone is not happy with $[Q \bullet f] \Big|_a^b$, he can find its annihilator $A$ and solve

$$ A \bullet P \bullet I(w) = 0 $$

Differentials and differences are interchangeable. In the first case one gets differential equation, in the second --- difference equation. Integrals and sums can also be switched, thus one can compute recurrence relations for sums as well as for integrals.

So what's algorithmic about this method? There are several algorithms to find $T$, though they are limited to the case $f$ being holonomic.

There is a nice package HolonomicFunctions for Mathematica. Follow the link for a profound introduction to the technique. I've just outlined the main idea here, probably incorrectly in certain parts.

As far as I know one of the algorithms for creative telescoping is also implemented in Mgfun package for Maple. If someone is aware about implementations for open source CAS's let us know here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.