×

Beyond polyhedral homotopies. (English) Zbl 1435.14053

Summary: We present a new algorithmic framework which utilizes tropical geometry and homotopy continuation for solving systems of polynomial equations where some of the polynomials are generic elements in linear subspaces of the polynomial ring. This approach generalizes the polyhedral homotopies by B. Huber and B. Sturmfels [Math. Comput. 64, No. 212, 1541–1555 (1995; Zbl 0849.65030)].

MSC:

14Q15 Computational aspects of higher-dimensional varieties
14T15 Combinatorial aspects of tropical varieties
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65H14 Numerical algebraic geometry

Citations:

Zbl 0849.65030
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allgower, E. L.; Georg, K., Introduction to numerical continuation methods, Classics in Applied Mathematics, vol. 45, (2003), SIAM · Zbl 1036.65047
[2] Bogart, T.; Jensen, A. N.; Speyer, D.; Sturmfels, B.; Thomas, R. R., Computing tropical varieties, J. Symb. Comput., 42, 1-2, 54-73, (2007), MR2284285 (2007j:14103) · Zbl 1121.14051
[3] Chen, Tianran; Lee, Tsung-Lin; Li, Tien-Yien, Hom4PS-3: a parallel numerical solver for systems of polynomial equations based on polyhedral homotopy continuation methods, (International Congress on Mathematical Software, (2014), Springer), 183-190 · Zbl 1434.65065
[4] Ghys, Étienne, A singular mathematical promenade, (2016), arXiv preprint · Zbl 1472.00001
[5] Gunji, Takayuki; Kim, Sunyoung; Kojima, Masakazu; Takeda, Akiko; Fujisawa, Katsuki; Mizutani, Tomohiko, Phom: a polyhedral homotopy continuation method for polynomial systems, Computing, 73, 1, 57-77, (2004) · Zbl 1061.65041
[6] Huber, Birkett; Sturmfels, Bernd, A polyhedral method for solving sparse polynomial systems, Math. Comput., 64, 212, 1541-1555, (1995), MR1297471 (95m:65100) · Zbl 0849.65030
[7] Jensen, Anders N., Gfan, a software system for Gröbner fans and tropical varieties, (2005-2018), Available at · Zbl 1148.68579
[8] Jensen, Anders Nedergaard, 2016. Tropical homotopy continuation.; Jensen, Anders Nedergaard, 2016. Tropical homotopy continuation.
[9] Jensen, Anders Nedergaard; Markwig, Hannah; Markwig, Thomas, An algorithm for lifting points in a tropical variety, Collect. Math., 59, 2, 129-165, (2008), MR2414142 (2009a:14077) · Zbl 1151.13021
[10] Jensen, Anders; Yu, Josephine, Stable intersections of tropical varieties, J. Algebraic Comb., 43, 1, 101-128, (2016), MR3439302 · Zbl 1406.14045
[11] Kaveh, Kiumars; Khovanskii, A. G., Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory, Ann. Math. (2), 176, 2, 925-978, (2012), MR2950767 · Zbl 1270.14022
[12] 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, (2008-2018), Available at · Zbl 1167.65366
[13] Maclagan, Diane; Sturmfels, Bernd, Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, (2015), American Mathematical Society Providence, RI · Zbl 1321.14048
[14] Morgan, Alexander, Solving polynomial systems using continuation for engineering and scientific problems, (1987), Prentice Hall Inc. Englewood Cliffs, NJ, MR1049872 (91c:00014) · Zbl 0733.65031
[15] Verschelde, J., Algorithm 795: phcpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 2, 251-276, (1999), Available at · Zbl 0961.65047
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.