Computing polynomial resultants: Bezout's determinant vs. Collins' reduced P.R.S. algorithm

ABSTRACT

Algorithms for computing the resultant of two polynomials in several variables, a key repetitive step of computation in solving systems of polynomial equations by elimination, are studied. Determining the best algorithm for computer implementation depends upon the extent to which extraneous factors are introduced, the extent of propagation of errors caused by truncation of real coeffcients, memory requirements, and computing speed. Preliminary considerations narrow the choice of the best algorithm to Bezout's determinant and Collins' reduced polynomial remainder sequence (p.r.s.) algorithm. Detailed tests performed on sample problems conclusively show that Bezout's determinant is superior in all respects except for univariate polynomials, in which case Collins' reduced p.r.s. algorithm is somewhat faster. In particular Bezout's determinant proves to be strikingly superior in numerical accuracy, displaying excellent stability with regard to round-off errors. Results of tests are reported in detail.

REFERENCES

• 1: ADLER, R. J., AND K.U, S. Y. A method of solving sets of non-linear algebraic equations. Progr. Rep. No. 3, NASA Grant NGR 36-003-021 to Case Inst. of Tech., Nov., 1966.
• 2: B6CHER, M. Introduction to Higher Algebra. Macmillan, New York, 1907, Chs. 15 and 16.
• 3: BROWN, W. S., HYDE, J. P., AND TAGUE, B.A. The ALPAK system for non-numerical algebra on a digital computer. BellSyst. Tech. J ., Pt. 1, 42 (Sept. 1963), 2081-2119; Pt. 2, 43 (Mar. 1964), 785--804; Pt. 3, 48 (July 1964), 1547-1562.
• 4: BURNSIDE, W. S., AND PANTON, A.W. The Theory o f Equations , 3rd ed. Longmans, Green and Co., London, 1892, Ch. 14.
• 5: G. E. Collins, PM, a system for polynomial manipulation, Communications of the ACM, v.9 n.8, p.578-589, Aug. 1966 [doi>10.1145/365758.365770]
• 6: --. Polynomial remainder sequences and determinants. Amer. Math. Mon. 73 (Aug.-Sept. 1966), 708-712.
• 7: 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]
• 8: COMIT Programmers Reference Manual, MIT Press, Cambridge, Mass., 1962.
• 9: DIGBY, D.W. Determinant (Algorithm 159). Comm. ACM 6, 3 (Mar., 1963), 104.
• 10: EMMER, E .J . Multiple solution sets for non-linear mechanics problems. Ph.D. Th., Case Inst. of Tech., June, 1966.
• 11: Paul E Hennion, Algorithm 170: reduction of a matrix containing polynomial elements, Communications of the ACM, v.6 n.4, p.165-166, April 1963 [doi>10.1145/366349.366451]
• 12: MACDUFFEE, C. C. Theory of Equations , Wiley, New York, 1954, Ch. 7.
• 13: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 14: MISHINA, A. P., AND PROSKURYAKOV, I .V . Higher Algebra . Pergamon, New York, 1965 (translated by Swinfen, A.).
• 15: Joel Moses, Solutions of systems of polynomial equations by elimination, Communications of the ACM, v.9 n.8, p.634-637, Aug. 1966 [doi>10.1145/365758.365802]
• 16: NEWELL, A. (Ed.) Information Processing Language--V Manual. Prentice-Hall, Englewood Cliffs, N. J., 1961.
• 17: Jaroslav Pfann , Josef Straka, Algorithm 269: determinant evaluation [F3], Communications of the ACM, v.8 n.11, p.668, Nov. 1965 [doi>10.1145/365660.365675]
• 18: Leo J. Rotenberg, Algorithm 224: Evaluation of determinant, Communications of the ACM, v.7 n.4, p.243-244, April 1964 [doi>10.1145/364005.364069]
• 19: Josef G. Solomon, Algorithms 41: Evaluation of determinant, Communications of the ACM, v.4 n.4, p.176, April 1961 [doi>10.1145/355578.366333]
• 20: TURNBILL, H. W. Theory of Equations , 5th ed. rev. Oliver and Boyd, Edinburgh and London, 1957, Ch. 11.
• 21: USPENSKY, J. -V. Theory of Equations , McGraw-Hill, New York, 1948, Ch. 12.
• 22: VAN DER WAERDEN, B. L. Modern Algebra, Vols. 1 and 2, 2nd ed., trans, by T. J. Benac. Frederick Ungar Pub. Co., New York, 1950, Chs. 4 and 11.
• 23: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 24: Leland H. Williams, Algebra of Polynomials in Several Variables for a Digital Computer, Journal of the ACM (JACM), v.9 n.1, p.29-40, Jan. 1962 [doi>10.1145/321105.321109]
• 25: W.u, C .L . Non-linear matrix algebra and engineering applications. Ph.D. Th., Case Inst. of Tech., 1964.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Multivariate statistics

General Terms:
Algorithms, Design, Theory

Keywords:
Bezout's determinant, Euclidean algorithm, Sylvester's determinant, elimination, g.c.d algorithm, multivariate polynomial equations, polynomial resultant, reduced p.r.s algorithm, resultant algorithm