×

Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods. (English) Zbl 1023.65048

Summary: Polyhedral homotopy continuation methods exploit the sparsity of polynomial systems so that the number of solution curves to reach all isolated solutions is optimal for generic systems. The numerical stability of tracing solution curves of polyhedral homotopies is mainly determined by the height of the powers of the continuation parameter. To reduce this height, we propose a procedure that operates as an intermediate stage between the mixed-volume computation and the tracing of solution curves. This procedure computes new lifting values of the support of a polynomial system. These values preserve the structure of the mixed-cell configuration obtained from the mixed-volume computation and procedure better-balanced powers of the continuation parameter in the polyhedral homotopies.

MSC:

65H10 Numerical computation of solutions to systems of equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
62H20 Measures of association (correlation, canonical correlation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.L. Allgower, K. Georg, Continuation and path following, Acta Numerica (1993) 1-64; E.L. Allgower, K. Georg, Continuation and path following, Acta Numerica (1993) 1-64 · Zbl 0792.65034
[2] Bernshtein, D. N., The number of roots of a system of equations, Functional Anal. Appl., 9, 183-185 (1975)
[3] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York, 1998; L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York, 1998 · Zbl 0872.68036
[4] P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic Complexity Theory, Springer, Berlin, 1997; P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic Complexity Theory, Springer, Berlin, 1997
[5] Emiris, I. Z.; Canny, J. F., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput., 20, 117-149 (1995) · Zbl 0843.68036
[6] I.M. Gel’fand, M.M. Kapranov, A.V. Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston, 1994; I.M. Gel’fand, M.M. Kapranov, A.V. Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston, 1994 · Zbl 0827.14036
[7] Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comp., 64, 1541-1555 (1995) · Zbl 0849.65030
[8] Li, T. Y., Numerical solutions of multivariate polynomial systems by homotopy continuation methods, Acta Numerica, 6, 399-436 (1997) · Zbl 0886.65054
[9] Michiels, T.; Verschelde, J., Enumerating regular mixed-cell configurations, Discrete Comput. Geom., 21, 569-579 (1999) · Zbl 0951.52012
[10] Morgan, A. P.; Wampler, C. W., Solving a planar four-bar design problem using continuation, ASME J. Mechanical Design, 112, 544-550 (1990)
[11] B. Mourrain, The handbook of polynomial systems, available at http://www.inria.fr/safir/ POL/index.html; B. Mourrain, The handbook of polynomial systems, available at http://www.inria.fr/safir/ POL/index.html · Zbl 0944.65054
[12] Sturmfels, B., On the Newton polytope of the resultant, J. Algebraic Combinatorics, 3, 207-236 (1994) · Zbl 0798.05074
[13] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8, AMS, Providence, RI, 1996; B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8, AMS, Providence, RI, 1996
[14] Verschelde, J.; Gatermann, K.; Cools, R., Mixed-volume computation by dynamic lifting applied to polynomial system solving, Discrete Comput. Geom., 16, 69-112 (1996) · Zbl 0854.68111
[15] Verschelde, J.; Verlinden, P.; Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31, 915-930 (1994) · Zbl 0809.65048
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.