Finding all solutions to a system of polynomial equations
Author:
Alden H. Wright
Journal:
Math. Comp. 44 (1985), 125133
MSC:
Primary 12D05; Secondary 65H10
MathSciNet review:
771035
Fulltext PDF Free Access
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). 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 YorkAmsterdam, 1967. MR 0240836
(39 #2181)
 [2]
S. N. Chow, J. MalletParet & 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, SpringerVerlag, Berlin and New York, 1979.
 [3]
Shui
Nee Chow, John
MalletParet, 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
(80d:55002), http://dx.doi.org/10.1090/S00255718197804920469
 [4]
F.
J. Drexler, A homotopy method for the calculation of all zeros of
zerodimensional polynomial ideals, Developments in statistics, Vol.
1, Academic Press, New York, 1978, pp. 69–93. MR 505422
(80f:58009)
 [5]
FranzJosef
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
(58 #3392)
 [6]
C.
B. García and T.
Y. Li, On the number of solutions to polynomial systems of
equations, SIAM J. Numer. Anal. 17 (1980),
no. 4, 540–546. MR 584729
(81m:65074), http://dx.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
(80f:65057), http://dx.doi.org/10.1007/BF01582106
 [8]
Morris
W. Hirsch, Differential topology, SpringerVerlag, New
YorkHeidelberg, 1976. Graduate Texts in Mathematics, No. 33. MR 0448362
(56 #6669)
 [9]
R.
W. Klopfenstein, Zeros of nonlinear functions, J. Assoc.
Comput. Mach. 8 (1961), 366–373. MR 0130113
(23 #B3145)
 [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 (84h:65056), http://dx.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. 7787.
 [1]
 R. Abraham & J. Robbin, Transversal Mappings and Flows, Benjamin, New York, 1967. MR 0240836 (39:2181)
 [2]
 S. N. Chow, J. MalletParet & 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, SpringerVerlag, Berlin and New York, 1979.
 [3]
 S. N. Chow, J. MalletParet & J. A. Yorke, "Finding zeros of maps: homotopy methods that are constructive with probability one," Math Comp., v. 32, 1978, pp. 887899. MR 492046 (80d:55002)
 [4]
 F. J. Drexler, "A homotopy method for the calculation of all zerodimensional polynomial ideals," Continuation Methods (H. Wacker, ed.), Academic Press, New York, 1978, pp. 6993. MR 505422 (80f:58009)
 [5]
 F. J. Drexler, "Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen," Numer. Math., v. 29, 1977, pp. 4558. 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. 540546. 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. 159176. MR 527572 (80f:65057)
 [8]
 M. Hirsch, Differential Topology, SpringerVerlag, New York, 1976. MR 0448362 (56:6669)
 [9]
 R. W. Klopfenstein, "Zeros of nonlinear functions," J. Assoc. Comput. Mach., v. 8, 1961, pp. 366373. 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. 131157. 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. 7787.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
12D05,
65H10
Retrieve articles in all journals
with MSC:
12D05,
65H10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198507710354
PII:
S 00255718(1985)07710354
Keywords:
Systems of nonlinear equations,
homotopy methods,
systems of polynomial equations
Article copyright:
© Copyright 1985
American Mathematical Society
