Algorithms for symbolic definite integration?

Solution 1:

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.