×
Zulehner, Walter

A simple homotopy method for determining all isolated solutions to polynomial systems. (English) Zbl 0637.65045

Math. Comput. 50, No. 181, 167-177 (1988).
Author’s summary: 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.
Reviewer: E.Allgower

Cited in 13 Documents

MSC:

65H10 Numerical computation of solutions to systems of equations

Keywords:

isolated solutions; homotopy method; systems of polynomial equations; numerical tests; computational cost
Cite Review PDF
Full Text: DOI

References:

[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. · Zbl 0432.65027 · doi: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. · Zbl 0543.65030 · doi: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. · Zbl 0427.65034
[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). · Zbl 0352.65023 · doi: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. · Zbl 0465.55003
[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. · Zbl 0408.90086 · doi: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. · Zbl 0409.65026 · doi: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. · Zbl 0428.90085
[9] Keith Kendig, Elementary algebraic geometry, Springer-Verlag, New York-Berlin, 1977. Graduate Texts in Mathematics, No. 44. · Zbl 0364.14001
[10] Masakazu Kojima and Shinji Mizuno, Computation of all solutions to a system of polynomial equations, Math. Programming 25 (1983), no. 2, 131 – 157. · Zbl 0517.90062 · doi: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. · Zbl 0395.65016 · doi: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.
[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. · Zbl 0538.65030
[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. · doi:10.1007/BF01390706
[15] Alexander P. Morgan, A homotopy for solving polynomial systems, Appl. Math. Comput. 18 (1986), no. 1, 87 – 92. · Zbl 0597.65046 · doi: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. · Zbl 0356.14002
[17] W. W. Wainberg & W. A. Trenogin, Theorie der Lösungsverzweigung bei nichtlinearen Gleichungen, Akademie-Verlag, Berlin, 1973. · Zbl 0266.45005
[18] Alden H. Wright, Finding all solutions to a system of polynomial equations, Math. Comp. 44 (1985), no. 169, 125 – 133. · Zbl 0567.55002
[19] W. Zulehner, Homotopy Methods for Determining All Isolated Solutions of Polynomial Systems, Institutsbericht Nr. 263, University of Linz, Austria, 1984, pp. 1-16.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.