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]**E. Allgower & K. Georg, "Simplicial and continuation methods for approximating fixed points and solutions to systems of equations,"*SIAM Rev.*, v. 22, 1980, pp. 28-85. 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. 397-418. MR**738385 (86c:58013)****[3]**S. N. Chow, J. Mallet-Paret & 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, Springer-Verlag, Berlin, 1979, pp. 77-78. MR**547982 (80k:58012)****[4]**F. J. Drexler, "Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungen,"*Numer. Math.*, v. 29, 1977, pp. 45-58. MR**0483386 (58:3392)****[5]**F. J. Drexler, "A homotopy-method for the calculation of all zeros of zero-dimensional polynomial ideals," in*Continuation Methods*(H. Wacker, ed.), Academic Press, New York, 1978, pp. 69-93. 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. 1-14. 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. 159-176. 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, Springer-Verlag, Berlin, 1980, pp. 481-497. MR**563880 (82a:65035)****[9]**K. Kendig,*Elementary Algebraic Geometry*, Springer-Verlag, 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. 131-157. 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. 37-62. 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. 11-39. MR**0474770 (57:14403)****[13]**T. Y. Li, "On Chow, Mallet-Paret and Yorke homotopy for solving systems of polynomials,"*Bull. Inst. Math. Acad. Sinica*, v. 11, 1983, pp. 433-437. 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. 283-289. MR**871230 (88c:65048)****[15]**A. Morgan, "A homotopy for solving polynomial systems,"*Appl. Math. Comput.*, v. 18, 1986, pp. 87-92. MR**815774 (87c:90194)****[16]**D. Mumford,*Algebraic Geometry*I:*Complex Projective Varieties*, Springer-Verlag, New York, 1976. MR**0453732 (56:11992)****[17]**W. W. Wainberg & W. A. Trenogin,*Theorie der Lösungsverzweigung bei nichtlinearen Gleichungen*, Akademie-Verlag, Berlin, 1973.**[18]**A. H. Wright, "Finding all solutions to a system of polynomial equations,"*Math. Comp.*, v. 44, 1985, pp. 125-133. 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. 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