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

DOI:
https://doi.org/10.1090/S0025-5718-1985-0771035-4

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 *n*th 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). 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.

**[1]**Ralph Abraham and Joel Robbin,*Transversal mappings and flows*, An appendix by Al Kelley, W. A. Benjamin, Inc., New York-Amsterdam, 1967. MR**0240836****[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]**Shui Nee Chow, John Mallet-Paret, and James A. Yorke,*Finding zeroes of maps: homotopy methods that are constructive with probability one*, Math. Comp.**32**(1978), no. 143, 887–899. MR**492046**, https://doi.org/10.1090/S0025-5718-1978-0492046-9**[4]**F. J. Drexler,*A homotopy method for the calculation of all zeros of zero-dimensional polynomial ideals*, Developments in statistics, Vol. 1, Academic Press, New York, 1978, pp. 69–93. MR**505422****[5]**Franz-Josef Drexler,*Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen*, Numer. Math.**29**(1977/78), no. 1, 45–58 (German, with English summary). MR**0483386**, https://doi.org/10.1007/BF01389312**[6]**C. B. García and Tien-Yian Li,*On the number of solutions to polynomial systems of equations*, SIAM J. Numer. Anal.**17**(1980), no. 4, 540–546. MR**584729**, https://doi.org/10.1137/0717046**[7]**C. B. García and W. I. Zangwill,*Finding all solutions to polynomial systems and other systems of equations*, Math. Programming**16**(1979), no. 2, 159–176. MR**527572**, https://doi.org/10.1007/BF01582106**[8]**Morris W. Hirsch,*Differential topology*, Springer-Verlag, New York-Heidelberg, 1976. Graduate Texts in Mathematics, No. 33. MR**0448362****[9]**R. W. Klopfenstein,*Zeros of nonlinear functions*, J. Assoc. Comput. Mach.**8**(1961), 366–373. MR**0130113**, https://doi.org/10.1145/321075.321080**[10]**Masakazu Kojima and Shinji Mizuno,*Computation of all solutions to a system of polynomial equations*, Math. Programming**25**(1983), no. 2, 131–157. MR**686876**, https://doi.org/10.1007/BF02591768**[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.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1985-0771035-4

Keywords:
Systems of nonlinear equations,
homotopy methods,
systems of polynomial equations

Article copyright:
© Copyright 1985
American Mathematical Society