A p-adic algorithm for univariate partial fractions

ABSTRACT

Partial fractions is an important algebraic operation with many applications in applied mathematics, physics and engineering. It is also an important operation in any computer symbolic and algebraic system. Among other things, it is used in the integration algorithm.

REFERENCES

• 1: W. S. Brown, The Subresultant PRS Algorithm, ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.237-249, Sept. 1978 [doi>10.1145/355791.355795]
• 2: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 3: P. Henrici, Applied and Computational Complex Analysis, Vol. 1, Wiley-Intersicence, N.Y. 1974, Chapter 7.
• 4: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 5: H. T. Kung and D. M. Tong, "Fast Algorithms for Partial Fraction Decomposition", Department of Computer Science report, Carnegie-Mellon University, Jan. 1976.
• 6: MACSYMA Reference Manual, "The MATHLAB Group", Laboratory for Computer Science, MIT, Cambridge, Mass., Dec. 1977.
• 7: J. Moses, "Symbolic Integration: The Stormy Decade", Trans. ACM, Vol. 139, May 1969, pp. 167-189.
• 8: R. Risch, "The Problem of Integration in Finite Terms", Bulletin of AMS, May 1970, pp. 605-608.
• 9: P. Wang, "An Improved Multivariate Polynomial Factoring Algorithm", Math Comp, vol. 32, No. 144, Oct. 1978, pp. 1215-1231.
• 10: P. Wang, "Parallel p-adic Construction in the Univariate Polynomial Factoring Algorithm", Proceedings, Second MACSYMA USERS CONFERENCE, Washington, D.C., June, 1979, pp. 310-317.
• 11: L. Weinberg, Network Analysis and Synthesis, McGraw-Hill, N.Y., 1962.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

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

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

General Terms:
Algorithms, Theory