On algorithms for solving systems of polynomial equations

ABSTRACT

Methods for finding numerical solutions of nonlinear algebraic systems of equations have been given considerable attention since the birth of the field of numerical analysis. The fact that these methods find many applications to problems in physics, engineering, economics, and mathematical theory of optimization cannot be overstressed. However, a significant number of these problems contain indeterminants or parameters, which should only be given numerical values at the very end of the computational processes. Sometimes numerical results simply cannot provide enough insight for the analysis of the problem. Furthermore, symbolic solutions via elimination theory provide not only all solutions to a given system of equations but also a classification of solutions into solution surfaces or parametrized solutions. Thus, the symbolic method can provide an infinite number of solutions where this feat is clearly impossible for the numerical methods.

REFERENCES

• 1: Berlekamp, E. R., "Factoring Polynomials over Finite Fields", <u>Bell System Technical Journal</u>, Vol. 46, 1967, MR #234, pp.1853--1859.
• 2: Bogen, R. A., <u>et al.</u>, MACSYMA User's Manual, Project MAC, M.I.T., Cambridge, Mass., June 1973.
• 3: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 4: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• 5: 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]
• 6: George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
• 7: Lee E. Heindel, Integer Arithmetic Algorithms for Polynomial Real Zero Determination, Journal of the ACM (JACM), v.18 n.4, p.533-548, Oct. 1971 [doi>10.1145/321662.321667]
• 8: Johnson, S. C., "Tricks for Improving Kronecker's Method", Bell Laboratories Report, 1966.
• 9: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 10: 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]
• 11: Lipson, J. D., "Symbolic Methods for the Computer Solution of Linear Equations with Application to Flowgraphs", <u>Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation</u>, Tobey, R. G., Editor, June 1969, pp. 233--303.
• 12: Michael T. McClellan, The exact solution of systems of linear equations with polynomial coefficients, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.399-414, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806311]
• 13: 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]
• 14: David Rea Musser, Algorithms for polynomial factorization., 1971
• 15: Joel Moses , David Y. Y. Yun, The EZ GCD algorithm, Proceedings of the annual conference, p.159-166, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805698]
• 16: Thomas, J. M., <u>Differential Systems</u>, American Mathematical Society, New York, 1937.
• 17: Van der Waerden, B. L., <u>Modern Algebra</u>, Vol. 1, Frederic Ungar Publishing Co., N. Y. 1949.
• 18: Wang, P. S. and Rothschild, L. P., "Factoring Multivariate Polynomials over the Integers", submitted to <u>Mathematics of Computation</u>, 1973.
• 19: Yun, D. Y. Y., "The Hensel Lemma in Symbolic Manipulation", Ph.D. Thesis, Department of Mathematics, M.I.T., (in preparation).