Abstract
A special homotopy continuation method, as a combination of the polyhedral homotopy and the linear product homotopy, is proposed for computing all the isolated solutions to a special class of polynomial systems. The root number bound of this method is between the total degree bound and the mixed volume bound and can be easily computed. The new algorithm has been implemented as a program called LPH using C++. Our experiments show its efficiency compared to the polyhedral or other homotopies on such systems. As an application, the algorithm can be used to find witness points on each connected component of a real variety.
The work is partly supported by the projects NSFC Grants 11471307, 11290141, 11271034, 61532019 and CAS Grant QYZDB-SSW-SYS026.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Garcia, C.B., Zangwill, W.I.: Finding all solutions to polynomial systems and other systems of equations. Math. Program. 16(1), 159–176 (1979)
Drexler, F.J.: Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen. Numer. Math. 29(1), 45–58 (1977)
Sommese, A.J., Verschelde, J., Wampler, C.W.: Numerical algebraic geometry. In: The Mathematical of Numerical Analysis. Lectures in Applied Mathematics, vol. 32, pp. 749–763. AMS (1996)
Allgower, E.L., Georg, K.: Introduction to numerical continuation methods. Reprint of the 1979 original. Society for Industrial and Applied Mathematics (2003)
Li, T.: Numerical solution of polynomial systems by homotopy continuation methods. In: Handbook of Numerical Analysis, vol. 11, pp. 209–304 Elsevier (2003)
Sommese, A.J., Wampler, C.W.: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific, Singapore (2005)
Morgan, A.: Solving Polynominal Systems Using Continuation for Engineering and Scientific Problems. Society for Industrial and Applied Mathematics, Philadelphia (2009)
Bates, D.J., Haunstein, J.D., Sommese, A.J., Wampler, C.W.: Numerically Solving Polynomial Systems with Bertini. Society for Industrial and Applied Mathematics, Philadelphia (2013)
Lee, T.L., Li, T.Y., Tsai, C.H.: Hom4ps-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method. Computing 83(2), 109 (2008)
Morgan, A.P., Sommese, A.J., Watson, L.T.: Finding all isolated solutions to polynomial systems using hompack. ACM Trans. Math. Softw. 15(2), 93–122 (1989)
Verschelde, J.: Algorithm 795: Phcpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25(2), 251–276 (1999)
Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 134–183. Springer, Heidelberg (1975). doi:10.1007/3-540-07407-4_17
Seidenberg, A.: A new decision method for elementary algebra. Ann. Math. 60(2), 365–374 (1954)
El Din, M.S., Schost, É.: Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In: Proceedings of ISSAC 2003, pp. 224–231. ACM, New York (2003)
El Din, M.S., Spaenlehauer, P.J.: Critical point computations on smooth varieties: degree and complexity bounds. In: Proceedings of ISSAC 2016, pp. 183–190. ACM, New York (2016)
Bank, B., Giusti, M., Heintz, J., Pardo, L.M.: Generalized polar varieties and an efficient real elimination. Kybernetika 40(5), 519–550 (2004)
Bank, B., Giusti, M., Heintz, J., Pardo, L.: Generalized polar varieties: geometry and algorithms. J. Complex. 21(4), 377–412 (2005)
Rouillier, F., Roy, M.F., El Din, M.S.: Finding at least one point in each connected component of a real algebraic set defined by a single equation. J. Complex. 16(4), 716–750 (2000)
El Din, M.S., Schost, É.: Properness defects of projections and computation of at least one point in each connected component of a real algebraic set. Discrete Comput. Geom. 32(3), 417–430 (2004)
Li, T.Y., Wang, X.: Solving real polynomial systems with real homotopies. Math. Comp. 60(202), 669–680 (1993)
Lu, Y., Bates, D.J., Sommese, A.J., Wampler, C.W.: Finding all real points of a complex curve. Technical report. In: Algebra, Geometry and Their Interactions (2006)
Bates, D.J., Sottile, F.: Khovanskii-rolle continuation for real solutions. Found. Comput. Math. 11(5), 563–587 (2011)
Besana, G.M., Rocco, S., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Cell decomposition of almost smooth real algebraic surfaces. Numer. Algorithms 63(4), 645–678 (2013)
Hauenstein, J.D.: Numerically computing real points on algebraic sets. Acta Appl. Math. 125(1), 105–119 (2013)
Shen, F., Wu, W., Xia, B.: Real root isolation of polynomial equations based on hybrid computation. In: Feng, R., Lee, W., Sato, Y. (eds.) Computer Mathematics, pp. 375–396. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43799-5_26
Wu, W., Reid, G.: Finding points on real solution components and applications to differential polynomial systems. In: Proceedings of ISSAC 2013, pp. 339–346. ACM, New York (2013)
Bernshtein, D.N.: The number of roots of a system of equations. Funct. Anal. Appl. 9(3), 183–185 (1975)
Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Regeneration homotopies for solving systems of polynomials. Math. Comp. 80(273), 345–377 (2011)
John, F.: Extremum problems with inequalities as subsidiary conditions. In: Giorgi, G., Kjeldsen, T.H. (eds.) Traces and Emergence of Nonlinear Programming, pp. 197–215. Springer, Basel (2014). doi:10.1007/978-3-0348-0439-4_9
Morgan, A.P., Sommese, A.J.: Coefficient-parameter polynomial continuation. Appl. Math. Comput. 29(2), 123–160 (1989)
Wu, W., Reid, G., Feng, Y.: Computing real witness points of positive dimensional polynomial systems. Theoretical Computer Science (2017). http://doi.org/10.1016/j.tcs.2017.03.035. Accessed 31 Mar 2017
Morgan, A.P., Sommese, A.J., Wampler, C.W.: A power series method for computing singular solutions to nonlinear analytic systems. Numer. Math. 63(1), 391–409 (1992)
Morgan, A.P.: A transformation to avoid solutions at infinity for polynomial systems. Appl. Math. Comput. 18(1), 77–86 (1986)
Huber, B., Verschelde, J.: Polyhedral end games for polynomial continuation. Numer. Algorithms 18(1), 91–108 (1998)
Bates, D.J., Hauenstein, J.D., Sommese, A.J.: A parallel endgame. Contemp. Math. 556, 25–35 (2011). AMS, Providence, RI
Acknowledgement
We gratefully acknowledge the very helpful suggestions of Hoon Hong on this paper with emphasis on Sect. 6. We also thank Changbo Chen for his helpful comments. And the authors would like to thank the anonymous reviewers for their constructive comments that greatly helped improving the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Wang, Y., Wu, W., Xia, B. (2017). A Special Homotopy Continuation Method for a Class of Polynomial Systems. In: Gerdt, V., Koepf, W., Seiler, W., Vorozhtsov, E. (eds) Computer Algebra in Scientific Computing. CASC 2017. Lecture Notes in Computer Science(), vol 10490. Springer, Cham. https://doi.org/10.1007/978-3-319-66320-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-66320-3_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-66319-7
Online ISBN: 978-3-319-66320-3
eBook Packages: Computer ScienceComputer Science (R0)