On Euclid's algorithm and the computation of polynomial greatest common divisors

ABSTRACT

This paper examines the computation of polynomial greatest common divisors by various generalizations of Euclid's algorithm. The phenomenon of coefficient growth is described, and the history of successful efforts first to control it and then to eliminate it is related. The recently developed modular algorithm is presented in careful detail, with special attention to the case of multivariate polynomials. The computing times for the subresultant PRS algorithm, which is essentially the best of its kind, and for the modular algorithm are analyzed, and it is shown that the modular algorithm is markedly superior. In fact, the modular algorithm can obtain a GCD in less time than is required to verify it by classical division.

REFERENCES

• 1: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 2: J. E. Sammet et al., Symbol Manipulation, Comm. ACM 9, 547-643 (August 66).
• 3: A. S. Householder, Bigradients and the Problem of Routh and Hurwitz, SIAM Review 10, 56-66 (January 1968).
• 4: A. S. Householder and G. W. Stewart, III, Bigradients, Hankel Determinants, and the Pads Table, pp. 131-150 of Constructive Aspects of the Fundamental Theorem of Algebra, edited by B. Dejon and P. Henrici, Wiley-Interscience, New York, 1969.
• 5: J.V. Uspensky, Theory of Equations, McGraw-Hill, New York, 1948.
• 6: 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]
• 7: W. S. Brown and J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, in preparation.
• 8: G. E. Collins, The Calculation of Multivariate Polynomial Resultants, to be published.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory