Numerical homotopies from Khovanskii bases

Burr, M.; Sottile, F.; Walker, E.

doi:10.1090/mcom/3689

Numerical homotopies from Khovanskii bases
HTML articles powered by AMS MathViewer

by M. Burr, F. Sottile and E. Walker HTML | PDF

Math. Comp. 92 (2023), 2333-2353 Request permission

Abstract:

We present numerical homotopy continuation algorithms for solving systems of equations on a variety in the presence of a finite Khovanskii basis. These homotopies take advantage of Anderson’s flat degeneration to a toric variety. When Anderson’s degeneration embeds into projective space, our algorithm is a special case of a general toric two-step homotopy algorithm. When Anderson’s degeneration is embedded in a weighted projective space, we explain how to lift to a projective space and construct an appropriate modification of the toric homotopy. Our algorithms are illustrated on several examples using Macaulay2.

References

Valery Alexeev and Michel Brion, Toric degenerations of spherical varieties, Selecta Math. (N.S.) 10 (2004), no. 4, 453–478. MR 2134452, DOI 10.1007/s00029-005-0396-8
Eugene L. Allgower and Kurt Georg, Numerical path following, Handbook of numerical analysis, Vol. V, Handb. Numer. Anal., V, North-Holland, Amsterdam, 1997, pp. 3–207. MR 1470225, DOI 10.1016/S1570-8659(97)80002-6
C. Améndola, J. Lindberg, and J. I. Rodriguez, Solving parameterized polynomial systems with decomposable projections, arXiv:1612.08807, 2016.
Dave Anderson, Okounkov bodies and toric degenerations, Math. Ann. 356 (2013), no. 3, 1183–1202. MR 3063911, DOI 10.1007/s00208-012-0880-3
D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, Bertini: software for numerical algebraic geometry, Available at http://bertini.nd.edu.
Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Numerically solving polynomial systems with Bertini, Software, Environments, and Tools, vol. 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3155500, DOI 10.1137/1.9781611972702
P. Breiding and S. Timme, HomotopyContinuation.jl: a package for homotopy continuation in Julia, Mathematical software—ICMS 2018 (J. Davenport, M. Kauers, G. Labahn, and J. Urban, eds.), Lecture Notes in Comput. Sci., vol. 10931, Springer, Cham, 2018, pp. 458–465.
M. Burr, O. Clarke, T. Duff, J. Leaman, N. Nichols, E. Walker, M. Stillman, and H. Tsai, SubalgebraBases, Macaulay 2 package, 2021.
Philippe Caldero, Toric degenerations of Schubert varieties, Transform. Groups 7 (2002), no. 1, 51–60. MR 1888475, DOI 10.1007/s00031-002-0003-4
T. Chen and R. Davis, A toric deformation method for solving Kuramoto equations on cycle networks, Nonlinear Dyn 109, 2203-2222 (2022), https://doi.org/10.1007/s11071-022-07550-z.
Tianran Chen, Tsung-Lin Lee, and Tien-Yien Li, Hom4PS-3: a parallel numerical solver for systems of polynomial equations based on polyhedral homotopy continuation methods, Mathematical software—ICMS 2014, Lecture Notes in Comput. Sci., vol. 8592, Springer, Heidelberg, 2014, pp. 183–190. MR 3334764, DOI 10.1007/978-3-662-44199-2_{3}0
David A. Cox, John B. Little, and Henry K. Schenck, Toric varieties, Graduate Studies in Mathematics, vol. 124, American Mathematical Society, Providence, RI, 2011. MR 2810322, DOI 10.1090/gsm/124
Igor Dolgachev, Weighted projective varieties, Group actions and vector fields (Vancouver, B.C., 1981) Lecture Notes in Math., vol. 956, Springer, Berlin, 1982, pp. 34–71. MR 704986, DOI 10.1007/BFb0101508
T. Duff, N. Hein, and F. Sottile, Certification for polynomial systems via square subsystems, J. Symbolic Comput. (2020).
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
David Eisenbud and Bernd Sturmfels, Binomial ideals, Duke Math. J. 84 (1996), no. 1, 1–45. MR 1394747, DOI 10.1215/S0012-7094-96-08401-X
D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
Birkett Huber, Frank Sottile, and Bernd Sturmfels, Numerical Schubert calculus, J. Symbolic Comput. 26 (1998), no. 6, 767–788. Symbolic numeric algebra for polynomials. MR 1662035, DOI 10.1006/jsco.1998.0239
Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541–1555. MR 1297471, DOI 10.1090/S0025-5718-1995-1297471-4
Deepak Kapur and Klaus Madlener, A completion procedure for computing a canonical basis for a $k$-subalgebra, Computers and mathematics (Cambridge, MA, 1989) Springer, New York, 1989, pp. 1–11. MR 1005954
Maria Kateri, Fatemeh Mohammadi, and Bernd Sturmfels, A family of quasisymmetry models, J. Algebr. Stat. 6 (2015), no. 1, 1–16. MR 3361388, DOI 10.18409/jas.v6i1.33
Kiumars Kaveh and A. G. Khovanskii, Mixed volume and an extension of intersection theory of divisors, Mosc. Math. J. 10 (2010), no. 2, 343–375, 479 (English, with English and Russian summaries). MR 2722802, DOI 10.17323/1609-4514-2010-10-2-343-375
Kiumars Kaveh and A. G. Khovanskii, Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory, Ann. of Math. (2) 176 (2012), no. 2, 925–978. MR 2950767, DOI 10.4007/annals.2012.176.2.5
Kiumars Kaveh and Christopher Manon, Khovanskii bases, higher rank valuations, and tropical geometry, SIAM J. Appl. Algebra Geom. 3 (2019), no. 2, 292–336. MR 3949692, DOI 10.1137/17M1160148
Robert Lazarsfeld and Mircea Mustaţă, Convex bodies associated to linear series, Ann. Sci. Éc. Norm. Supér. (4) 42 (2009), no. 5, 783–835 (English, with English and French summaries). MR 2571958, DOI 10.24033/asens.2109
Anton Leykin, Numerical algebraic geometry, J. Softw. Algebra Geom. 3 (2011), 5–10. MR 2881262, DOI 10.2140/jsag.2011.3.5
Alexander Morgan, Solving polynomial systems using continuation for engineering and scientific problems, Classics in Applied Mathematics, vol. 57, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. Reprint of the 1987 original [ MR1049872]; Pages 304–534: computer programs section, also available as a separate file online. MR 3396207, DOI 10.1137/1.9780898719031.pt1
Lorenzo Robbiano and Moss Sweedler, Subalgebra bases, Commutative algebra (Salvador, 1988) Lecture Notes in Math., vol. 1430, Springer, Berlin, 1990, pp. 61–87. MR 1068324, DOI 10.1007/BFb0085537
Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996. MR 1363949, DOI 10.1090/ulect/008
J. Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. on Math. Software 25 (1999), no. 2, 251–276.
Jan Verschelde, Pierre Verlinden, and Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31 (1994), no. 3, 915–930. MR 1275120, DOI 10.1137/0731049