Algorithms for partial fraction decomposition and rational function integration

ABSTRACT

Algorithms for symbolic partial fraction decomposition and indefinite integration of rational functions are described. Two types of partial fraction decomposition are investigated, square-free and complete square-free. A method is derived, based on the solution of a linear system, which produces the square-free decomposition of any rational function, say A/B. The computing time is shown to be O(n4(1n nf)2) where deg(A) <deg(B) &equil;n and f is a number which is closely related to the size of the coefficients which occur in A and B. The complete square-free partial fraction decomposition can then be directly obtained and it is shown that the computing time for this process is also bounded by O(n4(1n nf)2). A thorough analysis is then made of the classical method for rational function integration, due to Hermite. It is shown that the most efficient implementation of this method has a computing time of O(k3n5(1n nc) 2), where c is a number closely related to f and k is the number of square-free factors of B. A new method is then presented which avoids entirely the use of partial fraction decomposition and instead relies on the solution of an easily obtainable linear system. Theoretical analysis shows that the computing time for this method is O(n5 (in nf) 2) and extensive testing substantiates its superiority over Hermite's method.

REFERENCES

• 1: Collins, G. E., "Computing Time Analyses for Some Arithmetic and Algebraic Algorithms," Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, I.B.M. Corp., June, 1969.
• 2: Collins, G. E. and Horowitz, E., "The SAC-1 Partial Fraction Decomposition and Rational Function Integration System," Computer Sciences Department, University of Wisconsin, Technical Report No. 80, February, 1970.
• 3: Engelman, C., "MATHLAB: A Program For On-line Assistance in Symbolic Computations," Proceedings 1965 F.J.C.C., Spartan Books, Washington, D.C.
• 4: Hardy, G. H. The Integration of Functions of a Single Variable, second ed., Cambridge University Press, Cambridge, England 1916.
• 5: Hermite, Charles, Oeuvres de Charles Hermite, edited by Emil Picard, Vol. III, Paris, Gauthier-Villars, Imprimeur-Libraire, 1912.
• 6: Horowitz, Ellis. Algorithms for Symbolic Integration of Rational Functions, Ph.D. Dissertation, University of Wisconsin, Madison, Wisconsin, Nov. 1969.
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: Moses, Joel. Symbolic Integration. Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge, Mass., Sept. 1967.
• 9: Sammet, J. E. An annotated descriptor-based bibliography on the use of computers for doing non-numerical mathematics. Computing Reviews 7(1966), B1-B31.
• 10: Sammet, J. E. Modification No. 1 to an annotated descriptor-based bibliography on the use of computers for doing non-numerical mathematics. ACM SIGSAM Bulletin, No. 5(Dec. 1966) Appendix, pp. 1-19.
• 11: Tobey, R. G. Algorithms for Anti-Differentiation of Rational Functions, Ph.D. thesis, Harvard University, 1967.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

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

General Terms:
Algorithms, Performance, Theory