A simple homotopy method for determining all isolated solutions to polynomial systems
Author:
Walter Zulehner
Journal:
Math. Comp. 50 (1988), 167177
MSC:
Primary 65H10
MathSciNet review:
917824
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A new homotopy method for solving systems of polynomial equations is presented. The homotopy equation is extremely simple: It is linear with respect to the homotopy parameter and only one auxiliary parameter is needed to regularize the problem. Within some limits, an arbitrary starting problem can be chosen, as long as its solution set is known. No restrictions on the polynomial systems are made. A few numerical tests are reported which show the influence of the auxiliary parameter, resp. the starting problem, upon the computational cost of the method.
 [1]
Eugene
Allgower and Kurt
Georg, Simplicial and continuation methods for approximating fixed
points and solutions to systems of equations, SIAM Rev.
22 (1980), no. 1, 28–85. MR 554709
(81d:47040), http://dx.doi.org/10.1137/1022003
 [2]
Pavol
Brunovský and Pavol
Meravý, Solving systems of polynomial equations by bounded
and real homotopy, Numer. Math. 43 (1984),
no. 3, 397–418. MR 738385
(86c:58013), http://dx.doi.org/10.1007/BF01390182
 [3]
Shui
Nee Chow, John
MalletParet, and James
A. Yorke, A homotopy method for locating all zeros of a system of
polynomials, Functional differential equations and approximation of
fixed points (Proc. Summer School and Conf., Univ. Bonn, Bonn, 1978)
Lecture Notes in Math., vol. 730, Springer, Berlin, 1979,
pp. 77–88. MR 547982
(80k:58012)
 [4]
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)
 [5]
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)
 [6]
C.
B. García and W.
I. Zangwill, Determining all solutions to certain systems of
nonlinear equations, Math. Oper. Res. 4 (1979),
no. 1, 1–14. MR 543605
(80i:65054), http://dx.doi.org/10.1287/moor.4.1.1
 [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]
C.
B. García and W.
I. Zangwill, Global continuation methods for finding all solutions
to polynomial systems of equations in 𝑛 variables, Extremal
methods and systems analysis (Internat. Sympos., Univ. Texas, Austin, Tex.,
1977) Lecture Notes in Econom. and Math. Systems, vol. 174,
Springer, BerlinNew York, 1980, pp. 481–497. MR 563880
(82a:65035)
 [9]
Keith
Kendig, Elementary algebraic geometry, SpringerVerlag, New
YorkBerlin, 1977. Graduate Texts in Mathematics, No. 44. MR 0447222
(56 #5537)
 [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]
Masakazu
Kojima, Hisakazu
Nishino, and Naohiko
Arima, A PL homotopy for finding all the roots of a
polynomial, Math. Programming 16 (1979), no. 1,
37–62. MR
517759 (80g:55003), http://dx.doi.org/10.1007/BF01582093
 [12]
Harold
W. Kuhn, Finding roots of polynomials by pivoting, Fixed
points: algorithms and applications (Proc. First Internat. Conf., Clemson
Univ., Clemson, S.C., 1974) Academic Press, New York, 1977,
pp. 11–39. MR 0474770
(57 #14403)
 [13]
TienYien
Li, On Chow, MalletParet and Yorke homotopy for solving system of
polynomials, Bull. Inst. Math. Acad. Sinica 11
(1983), no. 3, 433–437. MR 726989
(85k:58015)
 [14]
T.Y.
Li and Tim
Sauer, Regularity results for solving systems of polynomials by
homotopy method, Numer. Math. 50 (1987), no. 3,
283–289. MR
871230 (88c:65048), http://dx.doi.org/10.1007/BF01390706
 [15]
Alexander
P. Morgan, A homotopy for solving polynomial systems, Appl.
Math. Comput. 18 (1986), no. 1, 87–92. MR 815774
(87c:90194), http://dx.doi.org/10.1016/00963003(86)900305
 [16]
David
Mumford, Algebraic geometry. I, SpringerVerlag, BerlinNew
York, 1976. Complex projective varieties; Grundlehren der Mathematischen
Wissenschaften, No. 221. MR 0453732
(56 #11992)
 [17]
W. W. Wainberg & W. A. Trenogin, Theorie der Lösungsverzweigung bei nichtlinearen Gleichungen, AkademieVerlag, Berlin, 1973.
 [18]
Alden
H. Wright, Finding all solutions to a system of
polynomial equations, Math. Comp.
44 (1985), no. 169, 125–133. MR 771035
(86i:12001), http://dx.doi.org/10.1090/S00255718198507710354
 [19]
W. Zulehner, Homotopy Methods for Determining All Isolated Solutions of Polynomial Systems, Institutsbericht Nr. 263, University of Linz, Austria, 1984, pp. 116.
 [1]
 E. Allgower & K. Georg, "Simplicial and continuation methods for approximating fixed points and solutions to systems of equations," SIAM Rev., v. 22, 1980, pp. 2885. MR 554709 (81d:47040)
 [2]
 P. Brunovský & P. Meravý, "Solving systems of polynomial equations by bounded and real homotopy," Numer. Math., v. 43, 1984, pp. 397418. MR 738385 (86c:58013)
 [3]
 S. N. Chow, J. MalletParet & J. A. Yorke, "A homotopy method for locating all zeros of a system of polynomials," in Functional Differential Equations and Approximation of Fixed Points (H.O. Peitgen and H.O. Walther, eds.), Lecture Notes in Math., vol. 730, SpringerVerlag, Berlin, 1979, pp. 7778. MR 547982 (80k:58012)
 [4]
 F. J. Drexler, "Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungen," Numer. Math., v. 29, 1977, pp. 4558. MR 0483386 (58:3392)
 [5]
 F. J. Drexler, "A homotopymethod for the calculation of all zeros of zerodimensional polynomial ideals," in Continuation Methods (H. Wacker, ed.), Academic Press, New York, 1978, pp. 6993. MR 505422 (80f:58009)
 [6]
 C. B. Garcia & W. I. Zangwill, "Determining all solutions to certain systems of nonlinear equations," Math. Oper. Res., v. 4, 1979, pp. 114. MR 543605 (80i:65054)
 [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]
 C. B. Garcia & W. I. Zangwill, "Global calculation methods for finding all solutions to polynomial systems of equations in n variables," in Extremal Methods and Systems Analysis (A. V. Fiacco and K. O. Kortanek, eds.), Lecture Notes in Econom. and Math. Systems, vol. 174, SpringerVerlag, Berlin, 1980, pp. 481497. MR 563880 (82a:65035)
 [9]
 K. Kendig, Elementary Algebraic Geometry, SpringerVerlag, Berlin and New York, 1977. MR 0447222 (56:5537)
 [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]
 M. Kojima, H. Nishino & N. Arima, "A PL homotopy for finding all roots of a polynomial," Math. Programming, v. 16, 1979, pp. 3762. MR 517759 (80g:55003)
 [12]
 H. W. Kuhn, "Finding roots of polynomials by pivoting," in Fixed Points: Algorithms and Applications, (S. Karamardian, ed.), Academic Press, New York, 1977, pp. 1139. MR 0474770 (57:14403)
 [13]
 T. Y. Li, "On Chow, MalletParet and Yorke homotopy for solving systems of polynomials," Bull. Inst. Math. Acad. Sinica, v. 11, 1983, pp. 433437. MR 726989 (85k:58015)
 [14]
 T. Y. Li & T. Sauer, "Regularity results for solving systems of polynomials by homotopy method," Numer. Math., v. 50, 1987, pp. 283289. MR 871230 (88c:65048)
 [15]
 A. Morgan, "A homotopy for solving polynomial systems," Appl. Math. Comput., v. 18, 1986, pp. 8792. MR 815774 (87c:90194)
 [16]
 D. Mumford, Algebraic Geometry I: Complex Projective Varieties, SpringerVerlag, New York, 1976. MR 0453732 (56:11992)
 [17]
 W. W. Wainberg & W. A. Trenogin, Theorie der Lösungsverzweigung bei nichtlinearen Gleichungen, AkademieVerlag, Berlin, 1973.
 [18]
 A. H. Wright, "Finding all solutions to a system of polynomial equations," Math. Comp., v. 44, 1985, pp. 125133. MR 771035 (86i:12001)
 [19]
 W. Zulehner, Homotopy Methods for Determining All Isolated Solutions of Polynomial Systems, Institutsbericht Nr. 263, University of Linz, Austria, 1984, pp. 116.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H10
Retrieve articles in all journals
with MSC:
65H10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809178247
PII:
S 00255718(1988)09178247
Keywords:
Systems of polynomial equations,
homotopy method
Article copyright:
© Copyright 1988
American Mathematical Society
