The calculation of multivariate polynomial resultants

ABSTRACT

An efficient algorithm is presented for the exact calculation of resultants of multivariate polynomials with integer coefficients. The algorithm applies modular homomorphisms and the Chinese remainder theorem, evaluation homomorphisms and interpolation, in reducing the problem to resultant calculation for univariate polynomials over GF(p), whereupon a polynomial remainder sequence algorithm is used. The computing time of the algorithm is analyzed theoretically as a function of the degrees and coefficient sizes of its inputs . As a very special case , it is shown that when all degrees are equal and the coefficient size is fixed, its computing time is approximately proportional to &lgr;2r+l , where &lgr; is the common degree and r is the number of variables . Empirically observed computing times of the algorithm are tabulated for a large number of examples, and other algorithms are compared. Potential application of the algorithm to the solution of systems of polynomial equations is briefly discussed.

REFERENCES

• 1: S. Gorn, FORTRAN vs. Basic FORTRAN: a programming language for informational processing on automatic data processing systems, Communications of the ACM, v.7 n.10, p.591-624, Oct. 1964 [doi>10.1145/364888.876694]
• 2: Bodewig, E., Matrix Calculus, North Holla Holland Publ. Co., 1959.
• 3: Brown, W. S ., The Compleat Euclidean Algorithm, Bell Telephone Laboratories Report, June 1968, 68 pages.
• 4: Butcher, J. C ., On Runge-Kutta Processes of High Order, J. Australian Math. Soc., Vol. 4 (1964), pp. 179-194.
• 5: Ceschino, F ., and J. Kuntzmann, Numerical Solution of Initial Value Problems, pp. 72-74, Prentice-Hall, 1966.
• 6: 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]
• 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: Collins, George E ., The SAC-1 Polynomial System, Univ. of Wisconsin Computing Center Technical Report No. 2, March 1968, 68 pages.
• 9: Collins, George E., L. E. Heindel, E. Horowitz, M. T. McClellan, and D. R. Musser, The SAC-1 Modular Arithmetic System, Univ. of Wisconsin Technical Report No. 10, June 1969, 50 pages.
• 10: George E. Collins, Letters to the editor: comment on a paper by Ku and Adler, Communications of the ACM, v.12 n.6, p.302-303, June 1969 [doi>10.1145/363011.363017]
• 11: Collins , George E., The SAC-1 Polynomial G.C.D. and Resultant System. In preparation.
• 12: George E. Collins, The SAC-1 system: An introduction and survey, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.144-152, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806279]
• 13: Lee E. Heindel, Integer arithmetic algorithms for polynomial real zero determination, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.415-426, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806312]
• 14: Jacobson, Nathan, Lectures in Abstract Algebra, Vol. III (Theory of Fields and Galois Theory), Van Nostrand, 1964.
• 15: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 16: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 17: Ku, S. Y., and R. J. Adler, Algebra-Based Methods for Solving Multivariate Polynomial Equations, Chemical Engineering Science Division Report No. 10-22-68, Case Western Reserve Univ ., 162 pages.
• 18: S. Y. Ku , R. J. Adler, Computing polynomial resultants: Bezout's determinant vs. Collins' reduced P.R.S. algorithm, Communications of the ACM, v.12 n.1, p.23-30, Jan. 1969 [doi>10.1145/362835.362839]
• 19: McClellan, Michael T ., Algorithms for Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Ph.D. Thesis, Computer Sciences Dept., Univ. of Wis. In preparation.
• 20: 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]
• 21: David Rea Musser, Algorithms for polynomial factorization., 1971
• 22: Takahasi, H ., and Y. Ishibashi, A New Method for Exact Calculation by Computer, Information Processing in Japan, Vol. 1 (1961), pp. 28-42.
• 23: Van der Waerden, B. L ., Modern Algebra, Vol. 1, Ungar Publ. Co ., 1948.

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.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory