×

Khovanskii-Rolle continuation for real solutions. (English) Zbl 1231.14047

Summary: We present a new continuation algorithm to find all real solutions to a nondegenerate system of polynomial equations. Unlike homotopy methods, the algorithm is not based on a deformation of the system; instead, it traces real curves connecting the solutions to one system of equations to those of another, eventually leading to the desired real solutions. It also differs from homotopy methods in that it follows only real paths and computes no complex solutions to the original equations. The number of curves traced is essentially bounded above by the fewnomial bound for real solutions, and the method takes advantage of any slack in that bound.

MSC:

14P05 Real algebraic sets
14Q99 Computational aspects in algebraic geometry
65H10 Numerical computation of solutions to systems of equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] E. Allgower, K. Georg, Introduction to Numerical Continuation Methods. Classics in Applied Mathematics, vol. 45 (SIAM, Philadelphia, 2003). · Zbl 1036.65047
[2] E. Allgower, M. Erdmann, K. Georg, On the complexity of exclusion algorithms for optimization, J. Complex. 18(2), 573–588 (2002). Algorithms and complexity for continuous problems/Algorithms, computational complexity, and models of computation for nonlinear and multivariate problems (Dagstuhl/South Hadley, MA, 2000). · Zbl 1005.68082 · doi:10.1006/jcom.2002.0638
[3] D.J. Bates, F. Bihan, F. Sottile, Bounds on the number of real solutions to polynomial equations, Int. Math. Res. Not. 2007(23), 7 (2007). Art. ID rnm114. · Zbl 1129.14077
[4] D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Adaptive precision path tracking, SIAM J. Numer. Anal. 46(2), 722–746 (2008). · Zbl 1162.65026 · doi:10.1137/060658862
[5] D.J. Bates, J.D. Hauenstein, M. Niemberg, F. Sottile, Computational aspects of Gale duality (2011, in progress).
[6] D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: Software for numerical algebraic geometry. Available at http://www.nd.edu/\(\sim\)sommese/bertini . · Zbl 1437.14005
[7] D.J. Bates, F. Sottile, Khovanskii–Rolle continuation for real solutions. www.math.tamu.edu/\(\sim\)sottile/stories/Rolle/ , www.nd.edu/\(\sim\)dbates1/Rolle/ . · Zbl 1231.14047
[8] F. Bihan, F. Sottile, New fewnomial upper bounds from Gale dual polynomial systems, Mosc. Math. J. 7(3), 387–407 (2007) 573. · Zbl 1148.14028
[9] F. Bihan, F. Sottile, Gale duality for complete intersections, Ann. Inst. Fourier 58(3), 877–891 (2008). · Zbl 1243.14044 · doi:10.5802/aif.2372
[10] G.E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, in Automata Theory and Formal Languages. Second GI Conf., Kaiserslautern, 1975. Lecture Notes in Comput. Sci., vol. 33 (Springer, Berlin, 1975), pp. 134–183.
[11] K. Georg, Improving the efficiency of exclusion algorithms, Adv. Geom. 1(2), 193–210 (2001). · Zbl 0982.65069
[12] G.-M. Greuel, G. Pfister, H. Schönemann, Singular 3.0, a computer algebra system for polynomial computations. Centre for Computer Algebra, University of Kaiserslautern, 2005. http://www.singular.uni-kl.de .
[13] B. Huber, J. Verschelde, Polyhedral end games for polynomial continuation, Numer. Algorithms 18(1), 91–108 (1998). · Zbl 0933.65057 · doi:10.1023/A:1019163811284
[14] A.G. Khovanskii, Fewnomials. Trans. of Math. Monographs, vol. 88 (AMS, Providence, 1991).
[15] J.B. Lasserre, M. Laurent, P. Rostalski, Semidefinite characterization and computation of zero-dimensional real radical ideals, Found. Comput. Math. 8(5), 607–647 (2008). · Zbl 1176.14010 · doi:10.1007/s10208-007-9004-y
[16] T. Lee, T.Y. Li, C. Tsai, Hom4ps-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method, Computing 83, 109–133 (2008). · Zbl 1167.65366 · doi:10.1007/s00607-008-0015-6
[17] A. Morgan, Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Classics in Applied Mathematics, vol. 57 (SIAM, Philadelphia, 2009). · Zbl 1170.65316
[18] B. Mourrain, J.-P. Pavone, Subdivision methods for solving polynomial systems. Technical report 5658, INRIA, 2005. · Zbl 1158.13010
[19] F. Rouillier, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput. 9(5), 433–461 (1999). · Zbl 0932.12008 · doi:10.1007/s002000050114
[20] A.J. Sommese, C.W. Wampler II, The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (World Scientific, Hackensack, 2005). · Zbl 1091.65049
[21] J. Verschelde, Algorithm 795, PHCpack, a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw. 25(2), 251–276 (1999). Software available at http://www.math.uic.edu/\(\sim\)jan . · Zbl 0961.65047 · doi:10.1145/317275.317286
[22] J.H. Wilkinson, Rounding Errors in Algebraic Processes (Dover, New York, 1994). · Zbl 0868.65027
[23] G.M. Ziegler, Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152 (Springer, New York, 1995). · Zbl 0823.52002
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.