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

Zulehner, Walter

doi:10.1090/S0025-5718-1988-0917824-7

A simple homotopy method for determining all isolated solutions to polynomial systems
HTML articles powered by AMS MathViewer

by Walter Zulehner PDF

Math. Comp. 50 (1988), 167-177 Request permission

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.

References

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, DOI 10.1137/1022003
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, DOI 10.1007/BF01390182
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
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 483386, DOI 10.1007/BF01389312
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
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, DOI 10.1287/moor.4.1.1
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, DOI 10.1007/BF01582106
C. B. García and W. I. Zangwill, Global continuation methods for finding all solutions to polynomial systems of equations in $n$ 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
Keith Kendig, Elementary algebraic geometry, Graduate Texts in Mathematics, No. 44, Springer-Verlag, New York-Berlin, 1977. MR 0447222
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, DOI 10.1007/BF02591768
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, DOI 10.1007/BF01582093
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
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
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, DOI 10.1007/BF01390706
Alexander P. Morgan, A homotopy for solving polynomial systems, Appl. Math. Comput. 18 (1986), no. 1, 87–92. MR 815774, DOI 10.1016/0096-3003(86)90030-5
David Mumford, Algebraic geometry. I, Grundlehren der Mathematischen Wissenschaften, No. 221, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties. MR 0453732

Theorie der Lösungsverzweigung bei nichtlinearen Gleichungen

Alden H. Wright, Finding all solutions to a system of polynomial equations, Math. Comp. 44 (1985), no. 169, 125–133. MR 771035, DOI 10.1090/S0025-5718-1985-0771035-4

Homotopy Methods for Determining All Isolated Solutions of Polynomial Systems