×

Some computational methods for systems of nonlinear equations and systems of polynomial equations. (English) Zbl 0759.65020

The paper presents a survey of computational methods for solving systems of nonlinear equations and, in particular, systems of polynomial equations. The emphasis is laid on simplicial algorithms and homotopy methods and, in fact, the material on other methods only consists of relatively general observations. After introductory comments, simplicial algorithms and their application are discussed and Kuhn’s method for finding all zeros of a polynomial is presented and analyzed. Then homotopy methods are introduced for general systems and considered in more detail for systems of polynomial equations. Some enhancements of known methods are suggested in the paper but no numerical details are included.

MSC:

65H10 Numerical computation of solutions to systems of equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
26C10 Real polynomials: location of zeros
12Y05 Computational aspects of field theory and polynomials (MSC2010)

Software:

PITCON; praxis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alexander, J. C. and J. A.Yorke (1978), The Homotopy Continuation Method: Numerically Implementable Topological Procedures, Transactions of the A.M.S. 242, 271-284. · Zbl 0424.58003 · doi:10.1090/S0002-9947-1978-0478138-5
[2] Allgower, E. L. and C. L.Keller (1971), A Search Routine for a Sperner Simplex, Computing 8, 157-165. · Zbl 0225.55004 · doi:10.1007/BF02234051
[3] Allgower, E. L. (1977), Application of a Fixed Point Algorithm to Nonlinear Boundary Value Problems Having Several Solutions, pp. 87-111, in Karamardian, S. (ed.), Fixed Points-Algorithms and Applications, Academic Press, New York. · Zbl 0424.90083
[4] Allgower, E. L. and K.Georg (1980), Simplical and Continuation Methods for Approximating Fixed Points, SIAM Review 22, 28-85. · Zbl 0432.65027 · doi:10.1137/1022003
[5] Allgower, E. L. and K.Georg (1990), Numerical Continuation Methods, Springer, Berlin. · Zbl 0717.65030
[6] Banach, S. (1922), Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales, Fund. Math. 3, 133-181. · JFM 48.0201.01
[7] Bézout, É. (1779), Théorie générale des équations algébriques, Ph.D. Pierres, Paris.
[8] Brent, R. P. (1971), Algorithms for Finding Zeros and Extrema of Functions without Calculating Derivatives, Report STAN-CS-71-198, Computer Science Department, Stanford University.
[9] Brooks, R. B. S., R. F.Brown, J.Pak, and D. H.Taylor (1975), Nielsen Number of Maps of Tori, Proc. A.M.S. 52, 398-400. · Zbl 0309.55005 · doi:10.1090/S0002-9939-1975-0375287-X
[10] Brouwer, L. E. J. (1912), Über Abbildungen von Mannigfaltigkeiten, Mathematische Annalen 71, 95-115. · JFM 42.0417.01
[11] Brouwer, L. E. J. (1952), An Intuitionist Correction of the Fixed-Point Theorem on the Sphere, Proc. Roy. Soc. London, Ser. A 213, 1-2. · Zbl 0046.40902 · doi:10.1098/rspa.1952.0106
[12] Brown, R. F. (1971), The Lefschetz Fixed Point Theorem, Scott, Foresman and Company, Glenview. · Zbl 0216.19601
[13] Cauchy, A. L. (1829), Exercises de mathématique, Oeuvres (2) 9, 122.
[14] Charnes, A., C. B.Garcia, and C. E.Lemke (1977), Constructive Proofs of Theorems Relating to: F(x)=y, with Applications, Mathematical Programming 12, 328-343. · Zbl 0363.65042 · doi:10.1007/BF01593801
[15] Chow, Shui-Nee, J.Mallet-Paret, and J. A.Yorke (1978), Finding Zeroes of Maps: Homotopy Methods that are Constructive with Probability One, Mathematics of Computation 32, 887-899. · Zbl 0398.65029 · doi:10.1090/S0025-5718-1978-0492046-9
[16] Cottle, R. W. (1982), Minimal Triangulation of the 4-Cube, Discrete Mathematics 40, 25-29. · Zbl 0483.52005 · doi:10.1016/0012-365X(82)90185-6
[17] Dang, Ch. (1989), The D1-Triangulation of R n for Simplicial Algorithms for Computing Solutions on Nonlinear Equations, Tilburg University, Center for Economic Research, Discussion paper No. 8928.
[18] Dang, Ch. (1990), The D2-Triangulation for Simplicial Homotopy Algorithms for Computing Solutions of Nonlinear Equations, Tilburg University, Center for Economic Research, Discussion paper No. 9024.
[19] Dang, Ch. and D. Talman (1990), The D1-Triangulation in Simplicial Variable Dimension Algorithms for Computing Solutions of Nonlinear Equations, Tilburg University, Center for Economic Research, Discussion paper No. 9027.
[20] Dang, Ch. (1990), The D3-Triangulation for Simplicial Deformation Algorithms for Computing Solutions of Nonlinear Equations, Tilburg University, Center for Economic Research, Discussion paper No. 8949.
[21] Davenport, J. H., Y.Siret et al. (1988), Computer Algebra, Academic Press, London.
[22] Debreu, G. (1959), Theory of Value, Yale University Press, New Haven. · Zbl 0193.20205
[23] Deschamps, P. J. (1977), Pricing for Congestion in Telephone Networks: A Numerical Example, pp. 473-494, in Karamardian, S. (ed.), Fixed Points-Algorithms and Applications, Academic Press, New York.
[24] Drexler, F. J. (1978), A Homotopy Method for the Calculation of All Zeros of Zero-Dimensional Polynomial Ideals, pp. 69-93, in Wacker, H. (ed.), Continuation Methods, Academic Press, New York. · Zbl 0465.55003
[25] Dugundji, J. and A.Granas (1982), Fixed Point Theory, Vol. 1, PWN-Polish Scientific Publishers, Warszawa. · Zbl 0483.47038
[26] Eaves, B. C. (1971), Computing Kakutani Fixed Points, SIAM J. Appl. Math. 21, 236-244. · Zbl 0224.52002 · doi:10.1137/0121027
[27] Eaves, B. C. (1984), A Course in Triangulations for Solving Equations with Deformations, Springer, Berlin. · Zbl 0558.65035
[28] Eaves, B. C., F. J.Gould, H. O.Peitgen, and M. J.Todd (1983), Homotopy Methods and Global Convergence, Plenum Press, New York. · Zbl 0507.00009
[29] Fan, Ky (1952), A Generalization of Tucker’s Combinatorial Lemma with Topological Applications, Ann. of Math. 56, 431-437. · Zbl 0047.42004 · doi:10.2307/1969651
[30] Fisher, M. L., F. J.Gould, and J. W.Tolle (1976), A Simplicial Approximation Algorithm for Solving Systems of Nonlinear Equations, Istituto Nazionale Di Alta Mathematica, Symposia Mathematica 19, 73-90. · Zbl 0334.65041
[31] Forster, W. (ed.) (1980), Numerical Solution of Highly Nonlinear Problems, North-Holland, Amsterdam. · Zbl 0416.00020
[32] Forster, W. (1980), Fifty Years of Further Development of a Combinatorial Lemma, Part C, in Forster, W. (ed.), Numerical Solution of Highly Nonlinear Problems, pp. 215-217, North-Holland, Amsterdam.
[33] Forster, W. (1984), Utilizing the Nielsen Number for Finding Multiple Solutions of Systems of Nonlinear Equations by Simplicial Fixed Point Algorithms, pp. 50-54, in Abstracts of the IIASA Workshop on Nondifferentiable Optimization: Motivations and Applications, International Institute for Applied Systems Analysis, Laxenburg, Austria
[34] Forster, W. (1987), Computing ?All? Solutions of Systems of Polynomial Equations by Simplicial Fixed Point Algorithms, pp. 39-57, in Talman, A. J. J. and G.van derLaan (eds.), The Computation and Modelling of Economic Equilibria, North-Holland, Amsterdam.
[35] Forster, W. (1988), Simplicial Fixed Point Algorithms and Systems of Polynomial Equations, p. 167, in Abstracts, The 13th International Symposium on Mathematical Programming, Tokyo.
[36] Freund, R. M. (1986), Combinatorial Theorems on the Simplotope that Generalize Results on the Simplex and Cube, Math. Oper. Res. 11, 169-179. · Zbl 0598.05024 · doi:10.1287/moor.11.1.169
[37] Garcia, C. B. and W. I.Zangwill (1979), Determining All Solutions to Certain Systems of Nonlinear Equations, Mathematics of Operations Research 4, 1-14. · Zbl 0408.90086 · doi:10.1287/moor.4.1.1
[38] Garcia, C. B. and W. I.Zangwill (1979), Finding All Solutions to Polynomial Systems and Other Systems of Equations, Mathematical Programming 16, 159-176. · Zbl 0409.65026 · doi:10.1007/BF01582106
[39] Garcia, C. B. and W. I.Zangwill (1980), Global Continuation Methods for Finding All Solutions to Polynomial Systems of Equations in n Variables, pp. 481-497, in Fiacco, A. V. and K. O.Kortanek (eds.), Extremal Methods in Systems Analysis, Lecture Notes in Economics and Mathematical Systems No 174, Springer, Berlin.
[40] Gould, F. J. (1980), Recent and Past Developments in the Simplicial Approximation Approach to Solving Nonlinear Equations?A Subjective View, pp. 466-480, in Fiacco, A. V. and K. O.Kortanek (eds.), Extremal Methods in Systems Analysis, Lecture Notes in Economics and Mathematical Systems No 174, Springer, Berlin. · Zbl 0432.90089
[41] Gould, F. J. and J. W.Tolle (1983), Complementary Pivoting on a Pseudomanifold Structure with Applications in the Decision Sciences, Heldermann Verlag, Berlin. · Zbl 0515.90053
[42] Guillemin, V. and A.Pollack (1974), Differential Topology, Prentice Hall, Englewood Cliffs. · Zbl 0361.57001
[43] Hartree, D. R. (1958), Numerical Analysis, Clarendon Press, Oxford. · Zbl 0082.11902
[44] Van der Heiden, L. (1979), Refinement Methods for Computing Fixed Points Using Primitive Sets, Yale University, Ph.D. thesis.
[45] Hopf, H. (1927), Über Mindestzahlen von Fixpunkten, Mathematische Zeitschrift 26, 762-774. · JFM 53.0554.01 · doi:10.1007/BF01475491
[46] Istratescu, V. I. (1981), Fixed Point Theory, D. Reidel, Dordrecht.
[47] Jiang, Boju (1980), Lectures on Nielsen Fixed Point Theory, American Mathematical Society, Providence. · Zbl 0455.55001
[48] Kakutani, S. (1941), A Generalization of Brouwer’s Fixed Point Theorem, Duke Mathematical Journal 8, 457-459. · Zbl 0061.40304 · doi:10.1215/S0012-7094-41-00838-4
[49] Karamardian, S. (1977), Fixed Points?Algorithms and Applications, Academic Press, New York. · Zbl 0409.00014
[50] Kojima, M. (1978), A Modification of Todd’s Triangulation J3, Math. Prog. 15, 223-227. · Zbl 0385.65029 · doi:10.1007/BF01609022
[51] Kojima, M. and Y.Yamamoto (1982), Variable Dimension Algorithms: Basic Theory, Interpretation, and Extensions of Some Existing Methods, Mathematical Programming 24, 177-215. · Zbl 0509.90070 · doi:10.1007/BF01585103
[52] Kojima, M. and S.Mizuno (1983), Computation of All Solutions to a System of Polynomial Equations, Mathematical Programming 25, 131-157. · Zbl 0517.90062 · doi:10.1007/BF02591768
[53] Kojima, M. (1988), Verbal Communication During a Meeting at the Tokyo Institute of Technology.
[54] Krasnosels’ Kii, M. A. (1964), Positive Solutions of Operator Equations, P. Noordhoff, Groningen.
[55] Kuhn, H. W. (1974), A New Proof of the Fundamental Theorem of Algebra, Mathematical Programming Study 1, 148-158. · Zbl 0364.30003
[56] Kuhn, H. W. and J. G.MacKinnon (1975), The Sandwich Method for Finding Fixed Points, J. Optimization Theory and Applications 17, 189-204. · Zbl 0299.65030 · doi:10.1007/BF00933874
[57] Kuhn, H. W. (1977), Finding Roots of Polynomials by Pivoting, pp. 11-39, in Karamardian, S. (ed.), Fixed Points-Algorithms and Applications, Academic Press, New York.
[58] Kuhn, H. W., Z.Wang, and S.Xu (1984), On the Cost of Computing Roots of Polynomials, Mathematical Programming 28, 156-163. · Zbl 0542.65025 · doi:10.1007/BF02612355
[59] Kuhn, H. W. (1988), Verbal Communication During a Meeting at Princeton University.
[60] Van derLaan, G. (1980), Simplicial Fixed Point Algorithms, Mathematisch Centrum, Amsterdam.
[61] Van derLaan, G. and A. J. J.Talman (1982), On the Computation of Fixed Points in the Product Space of Unit Simplices and an Application to Noncooperative N-Person Games, Math. Oper. Res. 7, 1-13. · Zbl 0497.90063 · doi:10.1287/moor.7.1.1
[62] Van derLaan, G., A. J. J.Talman, and L.van derHeyden (1987), Simplicial Variable Dimension Algorithms for Solving the Nonlinear Complementarity Problem on a Product of Unit Simplices Using General Labelling, Math. Oper. Res. 12, 377-397. · Zbl 0638.90096 · doi:10.1287/moor.12.3.377
[63] Li, T. Y. and N. H. Rhee (1988), Homotopy Algorithm for Symmetric Eigenvalue Problems, preprint. · Zbl 0653.65025
[64] Mara, P. S. (1976), Triangulations for the Cube, J. of Combinatorial Theory (A) 20, 170-177. · Zbl 0341.50001 · doi:10.1016/0097-3165(76)90014-5
[65] Maunder, C. R. F. (1970), Algebraic Topology, Van Nostrand, New York. · Zbl 0205.27302
[66] Merrill, O. H. (1972), Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-Continuous Point to Set Mappings, Univ. of Michigan, Ph.D. thesis.
[67] Miller, M. H. and J. E.Spencer (1977), The Static Economic Effects of the U.K. Joining the E.E.C.: A General Equilibrium Approach, The Review of Economic Studies 44, 71-93. · doi:10.2307/2296974
[68] Milnor, J. W. (1965), Topology from the Differentiable Viewpoint, The University Press of Virginia, Charlottesville. · Zbl 0136.20402
[69] Morgan, A. (1987), Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems, Prentice Hall, Englewood Cliffs. · Zbl 0733.65031
[70] Nielsen, J. (1921), Über die Minimalzahl der Fixpunkte bei den Abbildungstypen der Ringflächen, Mathematische Annalen 82, 83-93. · JFM 47.0527.03 · doi:10.1007/BF01457977
[71] Ortega, J. M. and W. C.Rheinboldt (1970), Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York. · Zbl 0241.65046
[72] Peitgen, H. O., D.Saupe et al. (1984), Cayley’s Problem and Julia Sets, The Mathematical Intelligencer 6, 11-20. · Zbl 0549.68101 · doi:10.1007/BF03024150
[73] Poincaré, H. (1884), Sur certaines solutions particulières du problème des trois corps, Bulletin Astronomique 1, 65-74. · JFM 15.0833.01
[74] Press, W. H., B. P.Flannery et al. (1989), Numerical Recipes in PASCAL, Cambridge University Press, Cambridge. · Zbl 0698.65001
[75] Renegar, J. (1985), On the Complexity of a Piecewise Linear Algorithm for Approximating Roots of Complex Polynomials, Mathematical Programming 32, 301-318 · Zbl 0577.65039 · doi:10.1007/BF01582051
[76] Renegar, J. (1985), On the Cost of Approximating all Roots of a Complex Polynomial, Mathematical Programming 32, 319-336. · Zbl 0577.65040 · doi:10.1007/BF01582052
[77] Rheinboldt, W. C. (1986), Numerical Analysis of Parameterized Nonlinear Equations, Wiley-Interscience, New York. · Zbl 0582.65042
[78] Rice, J. R. (1983), Numerical Methods, Software, and Analysis, IMSL Reference Edition, McGraw-Hill, New York.
[79] Robinson, S. M. (1980), Analysis and Computation of Fixed Points, Academic Press, New York. · Zbl 0463.00022
[80] Rourke, C. P. and B. J.Sanderson (1972), Introduction to Piecewise Linear Topology, Springer, Berlin. · Zbl 0254.57010
[81] Saigal, R. (1976), On Paths Generated by Fixed Point Algorithms, Mathematics of Oper. Res. 1, 359-380. · Zbl 0363.90092 · doi:10.1287/moor.1.4.359
[82] Sallee, J. F. (1982), A Note on Minimal Triangulations of an n-Cube, Discrete Applied Mathematics 4, 211-215. · Zbl 0489.52006 · doi:10.1016/0166-218X(82)90041-5
[83] Scarf, H. (1967), The Approximation of Fixed Points of a Continuous Mapping, SIAM J. Appl. Math. 15, 1328-1343. · Zbl 0153.49401 · doi:10.1137/0115116
[84] Scarf, H. and T.Hansen (1973), The Computation of Economic Equilibria, Yale University Press, New Haven. · Zbl 0311.90009
[85] Shoven, J. B. (1983), The Application of Fixed Point Methods to Economics, pp. 249-261, in Eaves, B. C. et al. (eds.), Homotopy Methods and Global Convergence, Plenum Press, New York. · Zbl 0523.90026
[86] Smale, S. (1976), A Convergent Process of Price Adjustment and Global Newton Methods, J. of Mathematical Economics 3, 107-120. · Zbl 0354.90018 · doi:10.1016/0304-4068(76)90019-7
[87] Smale, S. (1981), The Fundamental Theorem of Algebra and Complexity Theory, Bulletin of the A.M.S. 4, 1-36. · Zbl 0456.12012 · doi:10.1090/S0273-0979-1981-14858-8
[88] Smale, S. (1985), On the Efficiency of Algorithms of Analysis, Bulletin of the A.M.S. 13, 87-121. · Zbl 0592.65032 · doi:10.1090/S0273-0979-1985-15391-1
[89] Spanier, E. H. (1966), Algebraic Topology, TATA McGraw-Hill, Bombay. · Zbl 0145.43303
[90] Sperner, E. (1928), Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes, Abh. math. Sem. Hamburg 6, 265-272. · JFM 54.0614.01 · doi:10.1007/BF02940617
[91] Sperner, E. (1980), Fifty Years of Further Development of a Combinatorial Lemma, Part B, pp. 199-214, in Forster, W. (ed.), Numerical Solutions of Highly Nonlinear Problems, North-Holland, Amsterdam. · Zbl 0446.57033
[92] Talman, A. J. J. (1980), Variable Dimension Fixed Point Algorithms and Triangulations, Mathematisch Centrum, Amsterdam.
[93] Todd, M. J. (1976), The Computation of Fixed Points and Applications, Springer, Berlin. · Zbl 0332.54003
[94] Todd, M. J. and L.Tuncel (1990), A New Triangulation for Simplicial Algorithms, Technical Report No. 946, Cornell University, Ithaca, N.Y.
[95] Tucker, A. W. (1945), Some Topological Properties of Disk and Sphere, Proc. First Can. Math. Congress, Montreal, pp. 285-309.
[96] Tuy, H. (1979), Pivotal Methods for Computing Equilibrium Points: Unified Approach and New Restart Algorithm, Mathematical Programming 16, 210-227. · Zbl 0497.90059 · doi:10.1007/BF01582109
[97] Watson, L. T. (1986), Globally Convergent Homotopy Methods, SIAM Review 28, 529-545. · Zbl 0608.65028 · doi:10.1137/1028157
[98] Wright, A. H. (1981), The Octahedral Algorithm, A New Simplicial Fixed Point Algorithm, Mathematical Programming 21, 47-69. · Zbl 0475.65029 · doi:10.1007/BF01584229
[99] Yoseloff, M. (1974), Topological Proofs of Some Combinatorial Theorems, J. Comb. Thery (A) 17, 95-111. · Zbl 0365.05021 · doi:10.1016/0097-3165(74)90031-4
[100] Zeeman, E. C. (1963), Seminar on Combinatorial Topology, IHES, Mathematics Institute, University of Warwick, Coventry. · Zbl 0122.17901
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.