Symbolic Integration: The Algorithms

The pioneering paper about symbolic integration is:

Joel Moses:
Symbolic Integration: The Stormy Decade
Communications of the ACM, Vol 14, No 8 August 1971, pp. 548-650

This paper is an updated résumé of Moses' thesis 'Symbolic Integration', which is available at these addresses:

• Symbolic Integration reproduction of the article (PDF)
• Symbolic Integration - The Stormy Decade typoscript (PDF)

For persons with astrong interest in calculus, this paper is still enjoyable reading.

The full text of Moses' Ph.D. thesis can be found here:

• Full text of of Moses' thesis about symbolic integration (268 pages, PDF)

This thesis describes a three stage algorithm whose design is still followed by symbolic integrators of all major computer algebra systems.

A modern text about symbolic integration is:

Manuel Bronstein:
Symbolic Integration I Transcendental Functions
1997 Springer Berlin Heidelberg New York

The Integration Algorithm

The following description of the integration algorithm is taken from the ACM article (with substancial omissions):

First Stage

The first stage is a simple test to determine whether derivatives of a subexpression of the integrand divide the integrand. This test determines whether the integrand is of the form:

∫ c* op(u(x))*u'(x) dx

where

• c is a constant
• u(x) is some function of x
• u'(x) is its derivative
• op is an elementary function, namely one of
  • sin
  • cos
  • tan
  • cot
  • sec
  • csc
  • asin
  • atan
  • asec
  • log
  In addition, op(u(x)) can have the forms

  u(x)	(op being the identity)
  1/u(x)	(op being the reciprocal)
  u(x)d	where d <> -1
  du(x)	where d is a constant.

For integrands of this form, a table lookup and a substitution are sufficient to compute the integral.

Experience shows that this simple algorithm solves many integrals. The first stage examples demonstrate the power of the algorithm.

Second Stage

The algorithm enters the second stage when the first stage cannot solve the integral. The second stage contains eleven methods which might be applicable to a given problem. A pattern matching routine determines which methods should be attempted.

The eleven methods of the second stage are very specific and the applicability of each method can be quickly checked.

second stage examples.

Third Stage

The third stage is entered when the algorithms of the second stage cannot compute an integral. The third stage uses an incomplete implementation of the Risch algorithm to obtain an integral. When the third stage is unable to find an integral, the integration algorithm gives up and returns the noun form of the integral to compute.