Matías R. Bender
ABSTRACT
One of the biggest open problems in computational algebra is the design of efficient algorithms for Gröbner basis computations that take into account the sparsity of the input polynomials. We can perform such computations in the case of unmixed polynomial systems, that is systems with polynomials having the same support, using the approach of Faugère, Spaenlehauer, and Svartz [ISSAC'14]. We present two algorithms for sparse Gröbner bases computations for mixed systems. The first one computes with mixed sparse systems and exploits the supports of the polynomials. Under regularity assumptions, it performs no reductions to zero. For mixed, square, and 0-dimensional multihomogeneous polynomial systems, we present a dedicated, and potentially more efficient, algorithm that exploits different algebraic properties that performs no reduction to zero. We give an explicit bound for the maximal degree appearing in the computations.
- A. Awane, A. Chkiriba, and M. Goze. 2005. Formes d'inertie et complexe de Koszul associés à des polynômes plurihomogenes. Revista Matematica Complutense Vol. 18, 1 (2005), 243--260.Google Scholar
- D. Bayer and D. Mumford. 1993. What can be computed in algebraic geometry?. In Proc. Comp. Alg. Geom. and Commut. Algebra. Cambridge Univ. Press, 1--48.Google Scholar
- M. R. Bender, J.-C. Faugère, A. Mantzaflaris, and E. Tsigaridas. 2018. Bilinear systems with two supports: Koszul resultant matrices, eigenvalues, and eigenvectors. In Proc. ACM ISSAC. ACM, ACM. Google ScholarDigital Library
- F. Bihan and F. Sottile. 2011. Fewnomial bounds for completely mixed polynomial systems. Advances in Geometry Vol. 11, 3 (2011), 541--556.Google ScholarCross Ref
- N. Botbol. 2011. Implicitization of rational maps. Ph.D. Dissertation. bibinfoschoolUPMC.Google Scholar
- N. Botbol and M. Chardin. 2017. Castelnuovo Mumford regularity with respect to multigraded ideals. Journal of Algebra Vol. 474 (March. 2017), 361--392.Google ScholarCross Ref
- N. Bourbaki. 2007. Algèbre: chapitre 10. Algèbre homologique. Vol. Vol. 9. Springer.Google Scholar
- M. P. Brodmann and R. Y. Sharp. 2013. Local Cohomology: An Algebraic Introduction with Geometric Applications. Cambridge University Press.Google Scholar
- M. Chardin. 2007. Some results and questions on Castelnuovo-Mumford regularity. Lecture Notes in Pure and Applied Mathematics Vol. 254 (2007), 1.Google Scholar
- D. Cox, J. Little, and D. O'shea. 1992. Ideals, varieties, and algorithms. Springer.Google Scholar
- D. Cox, J. Little, and D. O'shea. 2006. Using algebraic geometry. Springer.Google Scholar
- D. Cox, J. Little, and H. Schenck. 2011. Toric varieties. AMS.Google Scholar
- C. D'Andrea. 2002. Macaulay style formulas for sparse resultants. Trans. Amer. Math. Soc. Vol. 354, 7 (2002), 2595--2629.Google ScholarCross Ref
- C. D'Andrea, T. Krick, and M. Sombra. 2013. Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze. Annales Scientifiques de l'École Normale Supérieure Vol. 46 (2013), 549--627.Google Scholar
- C. Eder and J.-C. Faugère. 2017. A survey on signature-based algorithms for computing Gröbner bases. Journal of Symbolic Computation Vol. 80 (2017), 719 -- 784.Google ScholarCross Ref
- D. Eisenbud. 2013. Commutative Algebra: with a view toward algebraic geometry. Vol. Vol. 150. Springer.Google Scholar
- M. S. El Din and É. Schost. 2017. Bit complexity for multi-homogeneous polynomial system solving - Application to polynomial minimization. Journal of Symbolic Computation (2017).Google Scholar
- I. Z. Emiris. 1996. On the complexity of sparse elimination. Journal of Complexity Vol. 12, 2 (1996), 134--166. Google ScholarDigital Library
- J. C. Faugère. 2002. A New Efficient Algorithm for Computing Gröbner Bases Without Reduction to Zero (F5) Proc. ACM ISSAC. ACM, 75--83. Google ScholarDigital Library
- J.-C. Faugère, M. S. El Din, and P.-J. Spaenlehauer. 2011. Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity. Journal of Symbolic Computation Vol. 46, 4 (2011), 406--437. Google ScholarDigital Library
- J.-C. Faugère, P. Gianni, D. Lazard, and T. Mora. 1993. Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation Vol. 16, 4 (1993), 329--344. Google ScholarDigital Library
- J.-C. Faugère, P.-J. Spaenlehauer, and J. Svartz. 2014. Sparse Gröbner bases: the unmixed case. In Proc. ACM ISSAC. ACM, 178--185. Google ScholarDigital Library
- I. M. Gelfand, M. Kapranov, and A. Zelevinsky. 2008. Discriminants, resultants, and multidimensional determinants. Springer.Google Scholar
- M. Giusti, G. Lecerf, and B. Salvy. 2001. A Gröbner free alternative for polynomial system solving. Journal of complexity Vol. 17, 1 (2001), 154--211. Google ScholarDigital Library
- H. T. Hà and A. Van Tuyl. 2004. The regularity of points in multi-projective spaces. Journal of Pure and Applied Algebra Vol. 187, 1--3 (March. 2004), 153--167.Google ScholarCross Ref
- J. D. Hauenstein and J. I. Rodriguez. 2015. Multiprojective witness sets and a trace test. arXiv preprint arXiv:1507.07069 (2015).Google Scholar
- M. I. Herrero, G. Jeronimo, and J. Sabia. 2013. Affine solution sets of sparse polynomial systems. Journal of Symbolic Computation Vol. 51 (2013), 34--54. Google ScholarDigital Library
- D. Lazard. 1983. Gröbner-Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations. In Proc. EUROCAL. Springer-Verlag, 146--156. Google ScholarDigital Library
- T.-Y. Li. 1997. Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta numerica Vol. 6 (1997), 399--436.Google Scholar
- D. Maclagan and G. G. Smith. 2004. Multigraded Castelnuovo-Mumford Regularity. J. Reine Angew. Math. Vol. 2004, 571 (Jan.. 2004).Google ScholarCross Ref
- D. Maclagan and G. G. Smith. 2005. Uniform bounds on multigraded regularity. J. Algebraic Geom. Vol. 14 (2005), 137--164. arXiv preprint math/0305215.Google ScholarCross Ref
- E. Miller and B. Sturmfels. 2004. Combinatorial commutative algebra. Springer.Google Scholar
- J. Sidman and A. Van Tuyl. 2006. Multigraded regularity: syzygies and fat points. Beitr"age Algebra Geom Vol. 47, 1 (2006), 67--87.Google Scholar
- B. Sturmfels. 1994. On the Newton polytope of the resultant. Journal of Algebraic Combinatorics Vol. 3, 2 (1994), 207--236. Google ScholarDigital Library
- B. Sturmfels and A. Zelevinsky. 1994. Multigraded resultants of Sylvester type. Journal of Algebra Vol. 163, 1 (1994), 115--127.Google ScholarCross Ref
- N. Trung. 1998. The Castelnuovo regularity of the Rees algebra and the associated graded ring. Trans. Amer. Math. Soc. Vol. 350, 7 (1998), 2813--2832.Google ScholarCross Ref
- B. Van der Waerden. 1978. On varieties in multiple-projective spaces. In Indagationes Mathematicae (Proceedings), Vol. 81. Elsevier, 303--312.Google Scholar
- J. Weyman and A. Zelevinsky. 1994. Multigraded formulae for multigraded resultants. J. Algebr. Geom Vol. 3, 4 (1994), 569--597.Google Scholar
Index Terms
- Towards Mixed Gröbner Basis Algorithms: the Multihomogeneous and Sparse Case
Recommendations
Gröbner Basis over Semigroup Algebras: Algorithms and Applications for Sparse Polynomial Systems
ISSAC '19: Proceedings of the 2019 on International Symposium on Symbolic and Algebraic ComputationGrö bner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial ...
Computing comprehensive Gröbner systems and comprehensive Gröbner bases simultaneously
ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computationIn Kapur et al (ISSAC, 2010), a new method for computing a comprehensive Grobner system of a parameterized polynomial system was proposed and its efficiency over other known methods was effectively demonstrated. Based on those insights, a new approach ...
The Gröbner basis algorithm and subresultant theory
ISSAC '94: Proceedings of the international symposium on Symbolic and algebraic computationWe investigate the possibility of constructing for Gro¨bner bases a concept similar to the one provided by subresultants for polynomial remainder sequences. Namely, we try to express the Gro¨bner basis polynomials obtained during the algorithm in terms ...
Comments