# How does Mathematica do symbolic integration?

I suppose there was at least once in our lifetime the point where we resorted to mathematica for help with an integral.-Unless you chose not to have the pleasure of using the continuum in your mathematical field of research.

I am wondering however whether behind a computer algebra system like mathematica that does symbolic computations there is some high-level idea how it would approach an awkward integral and try to find an anti-derivative?-I focus here on the integration part, since I think I would understand how to implement symbolic differentiation, at least conceptually, but integration seems to be rather mysterious to me.

• There is a Mathematica Stack Exchange site with many knowledgeable users, if you want to supplement the answers here. Mar 29 at 0:54
• I recommend anything written by Manuel Bronstein on the topic; e.g., his Symbolic Integration Tutorial or his book Symbolic Integration I: Transcendental Functions (unfortunately, he did not live to complete any further volumes). Mar 29 at 12:30
• I personally prefer Maple as don't like the user interface of Mathematica. They both have their own bugs and quirks which need to be worked around. Mar 30 at 0:10
• @HollisWilliams nice to see that salespeople for maple are also on mathoverflow. just kidding ;) Mar 30 at 0:23

An overview by one of the developers of Mathematica, focusing on definite integrals, is at Symbolic definite integration: methods and open issues.

Mathematica knows all the entries in Gradshteyn-Ryzhik, and more generally uses the Marichev-Adamchik Mellin transform to express the integral in terms of Meijer G functions, which are then simplified if possible. An example is worked out here.

Maple uses the Risch algorithm; see Keith Geddes and George Lebahn, Symbolic and numeric integration in Maple

• "Maple uses the Risch algorithm" --- well, sort of. Mar 28 at 20:39
• Since the OP did ask for a high level idea, might as well record that of the Risch anti-derivative algorithm here. The integrands are restricted to algebraic functions, extended by taking logs and exponentials. The restriction affords a canonical form. Knowing how to differentiate a canonical form, an intelligent ansatz for the anti-derivative can be made. The final result is obtained by a brute force search. The devil is in the details. Mar 28 at 20:49

People usually mention the Risch algorithm first, as other answers have.

Another approach, which is surprisingly successful, is to do what you or I would when solving integrals: look for patterns for which we have known-to-be-useful transformations. RUBI (which is usable from Mathematica as well as from other systems) does precisely this. According to its benchmarks, it works better than Mathematica's built-in Integrate.

This is why I was not surprised to see that machine-learning methods can also work very well. While I did not read the paper, I imagine that the inherent unpredictability/unreliability of such methods is not an issue: the result can always be verified by differentiation.

(Note: All I wrote above applies to indefinite integration. Definite integration is a different animal, and much harder problem, mostly because it is necessary to verify that the function behaves nicely in the middle of the integration interval.)

One approach to symbolic integration is using representations as Holonomic functions (https://en.wikipedia.org/wiki/Holonomic_function): solutions to differential equations of the form: $$p_r f^{(r)} + \cdots + p_i f^{(i)} + \cdots + p_0 f = 0$$ where the $$p_i$$ are polynomials.

Most functions you could want to antidifferentiate are holonomic, but not all (notably, not tan(x)).

Given such a representation (the list of polynomials), antidifferentiation is as simple as shifting the indices, so the problem comes down to translating to and from this representation.

Packages for working with holonomic functions are available for Mathematica and Maple

• Added: It's also worth noting that the problem of symbolic integration is undecidable due to en.wikipedia.org/wiki/Richardson's_theorem. The last step of the Risch algorithm (comparing derivatives of candidate antiderivatives to the original function) is undecidable. Mar 29 at 3:29