Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-25T05:31:12.012Z Has data issue: false hasContentIssue false
  • English
  • Français

Numerical solution of multivariate polynomial systems by homotopy continuation methods

Published online by Cambridge University Press:  07 November 2008

T. Y. Li
T. Y. Li
Affiliation:
Department of MathematicsMichigan State UniversityEast Lansing, MI 48824–1027USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

Let P(x) = 0 be a system of n polynomial equations in n unknowns. Denoting P = (p1,…, pn), we want to find all isolated solutions of

for x = (x1,…,xn). This problem is very common in many fields of science and engineering, such as formula construction, geometric intersection problems, inverse kinematics, power flow problems with PQ-specified bases, computation of equilibrium states, etc. Elimination theory-based methods, most notably the Buchberger algorithm (Buchberger 1985) for constructing Gröbner bases, are the classical approach to solving (1.1), but their reliance on symbolic manipulation makes those methods seem somewhat unsuitable for all but small problems.

Type
Research Article
Information
Acta Numerica , Volume 6 , January 1997 , pp. 399 - 436
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Allgower, E. L. (1984), Bifurcation arising in the calculation of critical points via homotopy methods, in Numerical Methods for Bifurcation Problems (Kupper, T., Mittelman, H. D. and Weber, H., eds), Birkhäuser, Basel, pp. 15–28.Google Scholar
Allgower, E. L. and Georg, K. (1990), Numerical Continuation Methods, an Introduction, Springer, Berlin. Springer Series in Computational Mathematics, Vol. 13.CrossRefGoogle Scholar
Allgower, E. L. and Georg, K. (1993), Continuation and path following, in Acta Numerica, Vol. 2, Cambridge University Press, pp. 1–64.Google Scholar
Allison, D. C. S., Chakraborty, A. and Watson, L. T. (1989), ‘Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube’, J. Supercomputing 3, 5–20.CrossRefGoogle Scholar
Bernshteín, D. N. (1975), ‘The number of roots of a system of equations’, Functional Anal. Appl. 9, 183–185. Translated from Funktsional. Anal. i Prilozhen., 9, 1–4.CrossRefGoogle Scholar
Brunovský, P. and Meravý, P. (1984), ‘Solving systems of polynomial equations by bounded and real homotopy’, Numer. Math. 43, 397–418.CrossRefGoogle Scholar
Buchberger, B. (1985), Gröbner basis: An algorithmic method in polynomial ideal theory, in Multidimensional System Theory (Bose, N., ed.), D. Reidel, Dordrecht, pp. 184–232.CrossRefGoogle Scholar
Canny, J. and Rojas, J. M. (1991), An optimal condition for determining the exact number of roots of a polynomial system, in Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ACM, pp. 96–101.Google Scholar
Chow, S. N., Mallet-Paret, J. and Yorke, J. A. (1979), Homotopy method for locating all zeros of a system of polynomials, in Functional Differential Equations and Approximation of Fixed Points (Peitgen, H. O. and Walther, H. O., eds), Lecture Notes in Mathematics, Vol. 730, Springer, Berlin, pp. 77–88.Google Scholar
Drexler, F. J. (1977), ‘Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen’, Numer. Math. 29, 45–58.CrossRefGoogle Scholar
Emiris, I. (1994), Sparse Elimination and Applications in Kinematics, PhD thesis, University of California at Berkeley.Google Scholar
Emiris, I. and Canny, J. (1995), ‘Efficient incremental algorithms for the sparse resultant and the mixed volume’, J. Symb. Computation 20, 117–149.Google Scholar
Fulton, W. (1984), Intersection Theory, Springer, Berlin.Google Scholar
Garcia, C. B. and Zangwill, W. I. (1979), ‘Finding all solutions to polynomial systems and other systems of equations’, Mathematical Programming 16, 159–176.CrossRefGoogle Scholar
Gel'fand, I. M., Kapranov, M. M. and Zelevinskií, A. V. (1994), Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston.CrossRefGoogle Scholar
Harimoto, S. and Watson, L. T. (1989), The granularity of homotopy algorithms for polynomial systems of equations, in Parallel Processing for Scientific Computing (Rodrigue, G., ed.), SIAM, Philadelphia.Google Scholar
Henderson, M. E. and Keller, H. B. (1990), ‘Complex bifurcation from real paths’, SIAM J. Appl. Math. 50, 460–482.Google Scholar
Huber, B. (software), Pelican Manual. Available via the author's web page, http://math.Cornell.edu/~birk.Google Scholar
Huber, B. and Sturmfels, B. (1995), ‘A polyhedral method for solving sparse polynomial systems’, Math. Comp. 64, 1541–1555.CrossRefGoogle Scholar
Huber, B. and Sturmfels, B. (1997), ‘Bernstein's theorem in affine space’, Discrete Comput. Geom. To appear.CrossRefGoogle Scholar
Khovanskií, A. G. (1978), ‘Newton polyhedra and the genus of complete intersections’, Functional Anal. Appl. 12, 38–46. Translated from Funktsional. Anal. i Prilozhen., 12, 51–61.Google Scholar
Kushnirenko, A. G. (1976), ‘Newton polytopes and the Bézout theorem’, Functional Anal. Appl. 10, 233–235. Translated from Funktsional. Anal. i Prilozhen., 10, 82–83.CrossRefGoogle Scholar
Lee, C. W. (1991), Regular triangulations of convex polytopes, in Applied Geometry and Discrete Mathematics – The Victor Klee Festschrift, DIMACS Series Vol. 4 (Gritzmann, P. and Sturmfels, B., eds), American Mathematical Society, Providence, RI, pp. 443–456.Google Scholar
Li, T. Y. (1983), ‘On Chow, Mallet-Paret and Yorke homotopy for solving systems of polynomials’, Bulletin of the Institute of Mathematics, Acad. Sin. 11, 433–437.Google Scholar
Li, T. Y. and Sauer, T. (1989), ‘A simple homotopy for solving deficient polynomial systems’, Japan J. Appl. Math. 6, 409–419.CrossRefGoogle Scholar
Li, T. Y. and Wang, X. (1990), A homotopy for solving the kinematics of the most general six- and-five-degree of freedom manipulators, in Proc. of ASME Conference on Mechanisms, Dl- Vol. 25, pp. 249–252.Google Scholar
Li, T. Y. and Wang, X. (1991), ‘Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant’, Math. Comp. 56, 693–710.Google Scholar
Li, T. Y. and Wang, X. (1992), ‘Nonlinear homotopies for solving deficient polynomial systems with parameters’, SIAM J. Numer. Anal. 29, 1104–1118.Google Scholar
Li, T. Y. and Wang, X. (1993), ‘Solving real polynomial systems with real homotopies’, Math. Comp. 60, 669–680.CrossRefGoogle Scholar
Li, T. Y. and Wang, X. (1994), ‘Higher order turning points’, Appl. Math. Comput. 64, 155–166.Google Scholar
Li, T. Y. and Wang, X. (1996), ‘The BKK root count in ℂn’, Math. Comp. 65, 1477–1484.CrossRefGoogle Scholar
Li, T. Y., Sauer, T. and Yorke, J. A. (1987 a), ‘Numerical solution of a class of deficient polynomial systems’, SIAM J. Numer. Anal. 24, 435–451.Google Scholar
Li, T. Y., Sauer, T. and Yorke, J. A. (1987 b), ‘The random product homotopy and deficient polynomial systems’, Numer. Math. 51, 481–500.CrossRefGoogle Scholar
Li, T. Y., Sauer, T. and Yorke, J. A. (1988), ‘Numerically determining solutions of systems of polynomial equations’, Bull. Amer. Math. Soc. 18, 173–177.CrossRefGoogle Scholar
Li, T. Y., Sauer, T. and Yorke, J. A. (1989), ‘The cheater's homotopy: an efficient procedure for solving systems of polynomial equations’, SIAM J. Numer. Anal. 26, 1241–1251.Google Scholar
Li, T. Y., Wang, T. and Wang, X. (1996), Random product homotopy with minimal BKK bound, in Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics on Mathematics of Numerical Analysis: Real Number Algorithms, Park City, Utah, pp. 503–512.Google Scholar
Malajovich, G. (software), pss 2.alpha, polynomial system solver, version 2.alpha, README file. Distributed by the author through gopher, http: www.labma.ufrj.br/;~gregorio.Google Scholar
Morgan, A. P. (1986), ‘A homotopy for solving polynomial systems’, Appl. Math. Comput. 18, 173–177.Google Scholar
Morgan, A. P. (1987), Solving Polynomial Systems using Continuation for Engineering and Scientific Problems, Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Morgan, A. P. and Sommese, A. J. (1987 a), ‘Computing all solutions to polynomial systems using homotopy continuation’, Appl. Math. Comput. 24, 115–138.Google Scholar
Morgan, A. P. and Sommese, A. J. (1987 b), ‘A homotopy for solving general polynomial systems that respect m-homogeneous structures’, Appl. Math. Comput. 24, 101–113.Google Scholar
Morgan, A. P. and Sommese, A. J. (1989), ‘Coefficient-parameter polynomial continuation’, Appl. Math. Comput. 29, 123–160. Errata: Appl. Math. Comput. 51, 207 (1992).Google Scholar
Morgan, A. P., Sommese, A. J. and Watson, L. T. (1989), ‘Finding all isolated solutions to polynomial systems using HOMPACK’, ACM Trans. Math. Software 15, 93–122.Google Scholar
Rojas, J. M. (1994), ‘A convex geometric approach to counting the roots of a polynomial system’, Theoret. Comput. Sci. 133, 105–140.Google Scholar
Rojas, J. M. and Wang, X. (1996), ‘Counting affine roots of polynomial systems via pointed Newton polytopes’, J. Complexity 12, 116–133.CrossRefGoogle Scholar
Shafarevich, I. R. (1977), Basic Algebraic Geometry, Springer, New York.Google Scholar
Shub, M. and Smale, S. (1993), ‘Complexity of Bézout's theorem I: Geometric aspects’, J. Amer. Math. Soc. 6, 459–501.Google Scholar
Tsai, L. W. and Morgan, A. P. (1985), ‘Solving the kinematics of the most general six-and five-degree-of-freedom manipulators by continuation methods’, ASME Journal of Mechanics, Transmissions, and Automation in Design 107, 189–200.CrossRefGoogle Scholar
Verschelde, J. (1995), PHC and MVC: two programs for solving polynomial systems by homotopy continuation, Technical report. Presented at the PoSSo workshop on software, Paris. Available by anonymous ftp to ftp.cs.kuleuven.ac.be in the directory /pub/NumAnal-ApplMath/PHC.Google Scholar
Verschelde, J. (1996), Homotopy continuation methods for solving polynomial systems, PhD thesis, Katholieke Universiteit Leuven, Belgium.Google Scholar
Verschelde, J. and Cools, R. (1993), ‘Symbolic homotopy construction’, Applicable Algebra in Engineering, Communication and Computing 4, 169–183.CrossRefGoogle Scholar
Verschelde, J. and Cools, R. (1994), ‘Symmetric homotopy construction’, J. Comput. Appl. Math. 50, 575–592.CrossRefGoogle Scholar
Verschelde, J. and Gatermann, K. (1995), ‘Symmetric Newton polytopes for solving sparse polynomial systems’, Adv. Appl. Math. 16, 95–127.CrossRefGoogle Scholar
Verschelde, J., Gatermann, K. and Cools, R. (1996), ‘Mixed volume computation by dynamic lifting applied to polynomial system solving’, Discrete Comput. Geom. 16, 69–112.CrossRefGoogle Scholar
Wampler, C. W. (1992), ‘Bézout number calculations for multi-homogeneous polynomial systems’, Appl. Math. Comput. 51, 143–157.Google Scholar
Wampler, C. W. (1994), ‘An efficient start system for multi-homogeneous polynomial continuation’, Numer. Math. 66, 517–523.Google Scholar
Wright, A. H. (1985), ‘Finding all solutions to a system of polynomial equations’, Math. Comp. 44, 125–133.CrossRefGoogle Scholar
Zulener, W. (1988), ‘A simple homotopy method for determining all isolated solutions to polynomial systems’, Math. Comp. 50, 167–177.Google Scholar