Toric eigenvalue methods for solving sparse polynomial systems

Bender, Matías; Telen, Simon

doi:10.1090/mcom/3744

Toric eigenvalue methods for solving sparse polynomial systems
HTML articles powered by AMS MathViewer

by Matías R. Bender and Simon Telen HTML | PDF

Math. Comp. 91 (2022), 2397-2429 Request permission

Abstract:

We consider the problem of computing homogeneous coordinates of points in a zero-dimensional subscheme of a compact, complex toric variety $X$. Our starting point is a homogeneous ideal $I$ in the Cox ring of $X$, which in practice might arise from homogenizing a sparse polynomial system. We prove a new eigenvalue theorem in the toric compact setting, which leads to a novel, robust numerical approach for solving this problem. Our method works in particular for systems having isolated solutions with arbitrary multiplicities. It depends on the multigraded regularity properties of $I$. We study these properties and provide bounds on the size of the matrices in our approach when $I$ is a complete intersection.

References

Klaus Altmann, Jarosław Buczyński, Lars Kastner, and Anna-Lena Winz, Immaculate line bundles on toric varieties, Pure Appl. Math. Q. 16 (2020), no. 4, 1147–1217. MR 4180245, DOI 10.4310/PAMQ.2020.v16.n4.a12
W. Auzinger and H. J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, Numerical mathematics, Singapore 1988, Internat. Schriftenreihe Numer. Math., vol. 86, Birkhäuser, Basel, 1988, pp. 11–30. MR 1022943
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
M. R. Bender. Algorithms for sparse polynomial systems: Groebner basis and resultants. PhD thesis, Sorbonne Université, June 2019.
Matías R. Bender, Jean-Charles Faugère, and Elias Tsigaridas, Towards mixed Gröbner basis algorithms: the multihomogeneous and sparse case, ISSAC’18—Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2018, pp. 71–78. MR 3840366, DOI 10.1145/3208976.3209018
M. R. Bender, J.-C. Faugère, and E. Tsigaridas, Gröbner basis over semigroup algebras: Algorithms and applications for sparse polynomial systems, Proceedings of the 44th International Symposium on Symbolic and Algebraic Computation, 2019.
Christine Berkesch, Daniel Erman, and Gregory G. Smith, Virtual resolutions for a product of projective spaces, Algebr. Geom. 7 (2020), no. 4, 460–481. MR 4156411, DOI 10.14231/ag-2020-013
Nicolás Botbol and Marc Chardin, Castelnuovo Mumford regularity with respect to multigraded ideals, J. Algebra 474 (2017), 361–392. MR 3595796, DOI 10.1016/j.jalgebra.2016.11.017
P. Breiding and S. Timme, Homotopycontinuation. jl: A package for homotopy continuation in Julia, In International Congress on Mathematical Software, pp. 458–465. Springer, 2018.
Peter Bürgisser and Felipe Cucker, Condition, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 349, Springer, Heidelberg, 2013. The geometry of numerical algorithms. MR 3098452, DOI 10.1007/978-3-642-38896-5
John Canny and Ioannis Emiris, An efficient algorithm for the sparse mixed resultant, Applied algebra, algebraic algorithms and error-correcting codes (San Juan, PR, 1993) Lecture Notes in Comput. Sci., vol. 673, Springer, Berlin, 1993, pp. 89–104. MR 1251972, DOI 10.1007/3-540-56686-4_{3}6
M. Chardin and N. Nemati. Multigraded regularity of complete intersections. arXiv:2012.14899 [math], Dec. 2020. arXiv: 2012.14899.
Robert M. Corless, Patrizia M. Gianni, and Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (Kihei, HI), ACM, New York, 1997, pp. 133–140. MR 1809979, DOI 10.1145/258726.258767
David A. Cox, The homogeneous coordinate ring of a toric variety, J. Algebraic Geom. 4 (1995), no. 1, 17–50. MR 1299003
David A. Cox, Applications of polynomial systems, CBMS Regional Conference Series in Mathematics, vol. 134, American Mathematical Society, Providence, RI, [2020] ©2020. With contributions by Carlos D’Andrea, Alicia Dickenstein, Jonathan Hauenstein, Hal Schenck and Jessica Sidman. MR 4284895
David A. Cox, Stickelberger and the eigenvalue theorem, Commutative algebra, Springer, Cham, [2021] ©2021, pp. 283–298. MR 4394411, DOI 10.1007/978-3-030-89694-2_{8}
David Cox and Alicia Dickenstein, Codimension theorems for complete toric varieties, Proc. Amer. Math. Soc. 133 (2005), no. 11, 3153–3162. MR 2160176, DOI 10.1090/S0002-9939-05-07956-6
David A. Cox, John Little, and Donal O’Shea, Using algebraic geometry, 2nd ed., Graduate Texts in Mathematics, vol. 185, Springer, New York, 2005. MR 2122859
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
Alicia Dickenstein and Ioannis Z. Emiris (eds.), Solving polynomial equations, Algorithms and Computation in Mathematics, vol. 14, Springer-Verlag, Berlin, 2005. Foundations, algorithms, and applications. MR 2161984, DOI 10.1007/b138957
T. Duff, S. Telen, E. Walker, and T. Yahl, Polyhedral homotopies in Cox coordinates. Preprint, arXiv:2012.04255, 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 Joe Harris, 3264 and all that—a second course in algebraic geometry, Cambridge University Press, Cambridge, 2016. MR 3617981, DOI 10.1017/CBO9781139062046
Mohamed Elkadi and Bernard Mourrain, Introduction à la résolution des systèmes polynomiaux, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 59, Springer, Berlin, 2007 (French). MR 2322065, DOI 10.1007/978-3-540-71647-1
Ioannis Z. Emiris, On the complexity of sparse elimination, J. Complexity 12 (1996), no. 2, 134–166. MR 1398322, DOI 10.1006/jcom.1996.0010
Ioannis Z. Emiris and Bernard Mourrain, Matrices in elimination theory, J. Symbolic Comput. 28 (1999), no. 1-2, 3–44. Polynomial elimination—algorithms and applications. MR 1709416, DOI 10.1006/jsco.1998.0266
Jean-Charles Faugère, Mohab Safey El Din, and Thibaut Verron, On the complexity of computing Gröbner bases for weighted homogeneous systems, J. Symbolic Comput. 76 (2016), 107–141. MR 3461262, DOI 10.1016/j.jsc.2015.12.001
William Fulton, Introduction to toric varieties, Annals of Mathematics Studies, vol. 131, Princeton University Press, Princeton, NJ, 1993. The William H. Roever Lectures in Geometry. MR 1234037, DOI 10.1515/9781400882526
I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
Huy Tài Hà, Multigraded regularity, $a^*$-invariant and the minimal free resolution, J. Algebra 310 (2007), no. 1, 156–179. MR 2307787, DOI 10.1016/j.jalgebra.2006.12.016
Huy Tài Hà and Adam Van Tuyl, The regularity of points in multi-projective spaces, J. Pure Appl. Algebra 187 (2004), no. 1-3, 153–167. MR 2027900, DOI 10.1016/j.jpaa.2003.07.006
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157, DOI 10.1007/978-1-4757-3849-0
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
George R. Kempf, Algebraic varieties, London Mathematical Society Lecture Note Series, vol. 172, Cambridge University Press, Cambridge, 1993. MR 1252397, DOI 10.1017/CBO9781107359956
Martin Kreuzer and Lorenzo Robbiano, Computational commutative algebra. 1, Springer-Verlag, Berlin, 2000. MR 1790326, DOI 10.1007/978-3-540-70628-1
Avinash Kulkarni, Solving $p$-adic polynomial systems via iterative eigenvector algorithms, Linear Multilinear Algebra 70 (2022), no. 4, 650–671. MR 4393631, DOI 10.1080/03081087.2020.1743633
D. Lazard, Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, Computer algebra (London, 1983) Lecture Notes in Comput. Sci., vol. 162, Springer, Berlin, 1983, pp. 146–156. MR 774807, DOI 10.1007/3-540-12868-9_{9}9
Diane Maclagan and Gregory G. Smith, Multigraded Castelnuovo-Mumford regularity, J. Reine Angew. Math. 571 (2004), 179–212. MR 2070149, DOI 10.1515/crll.2004.040
M. G. Marinari, H. M. Möller, and T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 103–145. MR 1223853, DOI 10.1007/BF01386834
César Massri, Solving a sparse system using linear algebra, J. Symbolic Comput. 73 (2016), 157–174. MR 3385957, DOI 10.1016/j.jsc.2015.06.003
H. Michael Möller and Hans J. Stetter, Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems, Numer. Math. 70 (1995), no. 3, 311–329. MR 1330867, DOI 10.1007/s002110050122
Bernard Mourrain, Simon Telen, and Marc Van Barel, Truncated normal forms for solving polynomial systems: generalized and efficient algorithms, J. Symbolic Comput. 102 (2021), 63–85. MR 4131450, DOI 10.1016/j.jsc.2019.10.009
Marta Panizzut, Emre Can Sertöz, and Bernd Sturmfels, An octanomial model for cubic surfaces, Matematiche (Catania) 75 (2020), no. 2, 517–536. MR 4151971, DOI 10.4418/2020.75.2.8
P. Pedersen and B. Sturmfels, Mixed monomial bases, Algorithms in algebraic geometry and applications (Santander, 1994) Progr. Math., vol. 143, Birkhäuser, Basel, 1996, pp. 307–316. MR 1414456
Mesut Şahin and Ivan Soprunov, Multigraded Hilbert functions and toric complete intersection codes, J. Algebra 459 (2016), 446–467. MR 3503981, DOI 10.1016/j.jalgebra.2016.04.013
Jessica Sidman and Adam Van Tuyl, Multigraded regularity: syzygies and fat points, Beiträge Algebra Geom. 47 (2006), no. 1, 67–87. MR 2245657
Jessica Sidman, Adam Van Tuyl, and Haohao Wang, Multigraded regularity: coarsenings and resolutions, J. Algebra 301 (2006), no. 2, 703–727. MR 2236764, DOI 10.1016/j.jalgebra.2005.09.032
Andrew J. Sommese and Charles W. Wampler II, The numerical solution of systems of polynomials, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. Arising in engineering and science. MR 2160078, DOI 10.1142/9789812567727
F. Sottile. Ibadan lectures on toric varieties. arXiv preprint arXiv:1708.01842, 2017.
Hans J. Stetter, Numerical polynomial algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004. MR 2048781, DOI 10.1137/1.9780898717976
Bernd Sturmfels, Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics, vol. 97, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2002. MR 1925796, DOI 10.1090/cbms/097
Simon Telen, Numerical root finding via Cox rings, J. Pure Appl. Algebra 224 (2020), no. 9, 106367, 26. MR 4083793, DOI 10.1016/j.jpaa.2020.106367
S. Telen, Solving systems of polynomial equations (doctoral dissertation), KU Leuven, Leuven, Belgium. retrieved from Lirias, 2020.
Simon Telen, Bernard Mourrain, and Marc Van Barel, Solving polynomial systems via truncated normal forms, SIAM J. Matrix Anal. Appl. 39 (2018), no. 3, 1421–1447. MR 3857888, DOI 10.1137/17M1162433
Simon Telen and Marc Van Barel, A stabilized normal form algorithm for generic systems of polynomial equations, J. Comput. Appl. Math. 342 (2018), 119–132. MR 3808461, DOI 10.1016/j.cam.2018.04.021
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