A Critical-pair/completion based integration algorithm

ABSTRACT

In 1976 Risch [1] proposed a scheme for finding the integrals of forms built up out of transcendental functions that viewed general functions as rational forms in a suitable differential field and represented the polynomial parts of those forms in a distributed rather than recursive way. By using a data representation where all variables were (more or less) equally important this new method seemed to side-step some of the complications that had appeared in his previous scheme [2] where various side-constraints had to be propagated between the levels present in a tower of separate extensions of differential fields, otherwise seen as levels in recursive datastructures. An initial implementation of the method was prepared in the context of the SCRATCHPAD/1 algebra system and demonstrated at the 1976 SYMSAC meeting at Yorktown Heights, a subsequent version for Reduce [3][5] came after that, and made it possible to try the method on a large range of integrals. These practical studies showed up some problems with the method and its implementation. The presentation given here re-expresses the 1976 Risch method in terms of rewrite rules, and thus exposes the major problem it suffers from as a manifestation of the fact that in certain circumstances the set of rewrites generated is not confluent. This difficulty is then attacked using a critical-pair/completion (CPC) approach. For very many integrands it is then easy to see that the initial set of rewrites used in the early implementations [1] and [3] do not need any extension, and this fact explains the high level of competence of the programs involved despite their shaky theoretical foundations. For a further large collection of problems even a simple CPC scheme converges rapidly; when the techniques presented here are applied to the REDUCE integration test suite in all applicable cases a short computation succeeds in completing the set of rewrites and hence gives a secure basis for testing for integrability. This paper describes the implementation of the CPC process and discusses current limitations to and possible future extended applications of it.

REFERENCES

• 1: Risch, R.H., 1976, report made at SYMSAC 76, Yorktown Heights.
• 2: Risch, R.H., 1969, "The problem of integration in finite terms" AMS 139 11
• 3: Norman, A.C. and Moore, P.M.A., "Implementing the new Risch Integration Algorithm", 1977, proc St. Maximim Conference on computer algebra.
• 4: Harrington, S..i. "A new symbolic integration system for REDUCE", 1979, Computer Journal 22.
• 5: Hearn, A.C., the REDUCE ~lgebra system
• 6: Buehburger, B. and Lcsos, R., "Algebraic simplification", in {9} pp 36-38
• 7: Fitch, J.P., Hearn, A.C., Davenport, J.H., Norman, A.C, Moore, P.M.A., code present in the REDUCE 3.3 integration modul ~
• 8: Rothstein, M. ar,~ Caviness, B., 1979, "A Structure Theorem for ex,pc~-~ential and primitive functions", SIAM J Computi~g 8/3, 357-6'/
• 9: B. Buchberger , George E. Collins , Rudiger Loos , Rudolf Albrecht, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 10: J. H. Davenport , B. M. Trager, On the parallel Risch Algorithm (II), ACM Transactions on Mathematical Software (TOMS), v.11 n.4, p.356-362, Dec. 1985 [doi>10.1145/6187.6189]
• 11: John Fitch, User-based integration software, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.245-248, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806404]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

          Nouns: REDUCE

General Terms:
Algorithms, Experimentation