Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Finding all solutions to a system of polynomial equations

Author: Alden H. Wright
Journal: Math. Comp. 44 (1985), 125-133
MSC: Primary 12D05; Secondary 65H10
MathSciNet review: 771035
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a polynomial equation of degree d over the complex domain, the Fundamental Theorem of Algebra tells us that there are d solutions, assuming that the solutions are counted by multiplicity. These solutions can be approximated by deforming a standard nth degree equation into the given equation, and following the solutions through the deformation. This is called the homotopy method. The Fundamental Theorem of Algebra can be proved by the same technique.

In this paper we extend these results and methods to a system of n polynomial equations in n complex variables. We show that the number of solutions to such a system is the product of the degrees of the equations (assuming that infinite solutions are included and solutions are counted by multiplicity)$ ^\ast$. The proof is based on a homotopy, or deformation, from a standard system of equations with the same degrees and known solutions. This homotopy provides a computational method of approximating all solutions. Computational results demonstrating the feasibility of this method are also presented.

References [Enhancements On Off] (What's this?)

  • [1] R. Abraham & J. Robbin, Transversal Mappings and Flows, Benjamin, New York, 1967. MR 0240836 (39:2181)
  • [2] S. N. Chow, J. Mallet-Paret & J. A. Yorke, "A homotopy method for locating all zeros of a system of polynomials," Functional Differential Equations and Approximation of Fixed Points (Proceedings, Bonn, 1978), Lecture Notes in Math., Vol. 730, Springer-Verlag, Berlin and New York, 1979.
  • [3] S. N. Chow, J. Mallet-Paret & J. A. Yorke, "Finding zeros of maps: homotopy methods that are constructive with probability one," Math Comp., v. 32, 1978, pp. 887-899. MR 492046 (80d:55002)
  • [4] F. J. Drexler, "A homotopy method for the calculation of all zero-dimensional polynomial ideals," Continuation Methods (H. Wacker, ed.), Academic Press, New York, 1978, pp. 69-93. MR 505422 (80f:58009)
  • [5] F. J. Drexler, "Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen," Numer. Math., v. 29, 1977, pp. 45-58. MR 0483386 (58:3392)
  • [6] C. B. Garcia & T. Y. Li, "On the number of solutions to polynomial systems of equations," SIAM J. Numer. Anal., v. 17, 1980, pp. 540-546. MR 584729 (81m:65074)
  • [7] C. B. Garcia & W. I. Zangwill, "Finding all solutions to polynomial systems and other systems of equations," Math. Programming, v. 16, 1979, pp. 159-176. MR 527572 (80f:65057)
  • [8] M. Hirsch, Differential Topology, Springer-Verlag, New York, 1976. MR 0448362 (56:6669)
  • [9] R. W. Klopfenstein, "Zeros of non-linear functions," J. Assoc. Comput. Mach., v. 8, 1961, pp. 366-373. MR 0130113 (23:B3145)
  • [10] M. Kojima & S. Mizuno, "Computation of all solutions to a system of polynomial equations," Math. Programming, v. 25, 1983, pp. 131-157. MR 686876 (84h:65056)
  • [11] B. L. van der Waerden, "Die Alternative bei nichtlinearen Gleichungen," Nachrichten der Gesellschaft der Wissenschaften zu Göttingen, Math. Phys. Klasse, 1928, pp. 77-87.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12D05, 65H10

Retrieve articles in all journals with MSC: 12D05, 65H10

Additional Information

Keywords: Systems of nonlinear equations, homotopy methods, systems of polynomial equations
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society