A simple homotopy method for determining all isolated solutions to polynomial systems

Author:
Walter Zulehner

Journal:
Math. Comp. **50** (1988), 167-177

MSC:
Primary 65H10

DOI:
https://doi.org/10.1090/S0025-5718-1988-0917824-7

MathSciNet review:
917824

Full-text PDF

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**, https://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**, https://doi.org/10.1007/BF01390182**[3]**Shui Nee Chow, John Mallet-Paret, 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****[4]**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**[5]**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****[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**, https://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**, https://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, Berlin-New York, 1980, pp. 481–497. MR**563880****[9]**Keith Kendig,*Elementary algebraic geometry*, Springer-Verlag, New York-Berlin, 1977. Graduate Texts in Mathematics, No. 44. MR**0447222****[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]**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**, https://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****[13]**Tien-Yien Li,*On Chow, Mallet-Paret and Yorke homotopy for solving system of polynomials*, Bull. Inst. Math. Acad. Sinica**11**(1983), no. 3, 433–437. MR**726989****[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**, https://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**, https://doi.org/10.1016/0096-3003(86)90030-5**[16]**David Mumford,*Algebraic geometry. I*, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties; Grundlehren der Mathematischen Wissenschaften, No. 221. MR**0453732****[17]**W. W. Wainberg & W. A. Trenogin,*Theorie der Lösungsverzweigung bei nichtlinearen Gleichungen*, Akademie-Verlag, 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**, https://doi.org/10.1090/S0025-5718-1985-0771035-4**[19]**W. Zulehner,*Homotopy Methods for Determining All Isolated Solutions of Polynomial Systems*, Institutsbericht Nr. 263, University of Linz, Austria, 1984, pp. 1-16.

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

Retrieve articles in all journals with MSC: 65H10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1988-0917824-7

Keywords:
Systems of polynomial equations,
homotopy method

Article copyright:
© Copyright 1988
American Mathematical Society