Gröbner Bases, Resultants and Polyhedral Geometry - GRAPE

Funded by: Bilateral Project with France - TUBITAK 2509
Grant amount: ~50k euro
Period: 2019 Jun - 2022 Jun
Principal Investigator: Zafeirakis Zafeirakopoulos, Ayesha Asloob Qureshi, Elias Tsigaridas (INRIA Paris, French side)

Project details

GRAPE is about the use of polyhedral methods in the theory of sparse polynomial systems. The goal is to combine polyhedral and toric geometry with the study of sparse systems and especially concerning resultants and Gröbner bases. In the Turkish side of the project we focus on the polyhedral aspects. In particular we generalize the notion of Newton polytope to that of Newton fan. Instead of considering all polynomials having a given Newton polytope, we consider all polynomials whose Newton polytopes have the same normal fan. Then, we study a multivariate version of Hilbert series and connect to the generating functions of linear Diophantine systems. Finally, in the context of toric geometry, we study the Hilbert series and other characteristics of ideals coming from graphs. Of particular interest is the study of Newton polytopes of edge rings. The main goal of the international collaboration is the derivation of better algorithms and complexity bounds for sparse resultants and Gröbner bases. Last year, members of the French team presented a first step towards this goal. It is clear that more polyhedral geometry is needed in order to proceed and this is what this project is about. Bringing together two complementary teams in order to work on a state-of-the-art topic. But instead of trying to improve the existing result only, what we suggest is a generalization of the framework as well.

Publications in the context of GRAPE:

Ioannis Emiris, Angelos Mantzaflaris, Elias Tsigaridas. Multilinear Polynomial Systems: Root Isolation and Bit Complexity. Journal of Symbolic Computation, Elsevier, In press, Special Issue on Milestones in Computer Algebra (MICA 2016). , 2019

Evangelos Bartzos, Ioannis Emiris, Jan Legersky, Elias Tsigaridas. On the maximal number of real embeddings of minimally rigid graphs in R^2, R^3 and S^2. Journal of Symbolic Computation, Elsevier, In press, 2019 <10.1016/j.jsc.2019.10.015>.

Ioannis Emiris, Bernard Mourrain, Elias Tsigaridas. Separation bounds for polynomial systems. Journal of Symbolic Computation, Elsevier, 2019, <10.1016/j.jsc.2019.07.001>.

Matias Bender, Jean-Charles Faugere, Elias Tsigaridas. Grobner Basis over Semigroup Algebras: Algo- ̈ rithms and Applications for Sparse Polynomial Systems. ISSAC 2019 - 44th International Symposium on Symbolic and Algebraic Computation, Jul 2019, Beijing, China. pp.42-49, <10.1145/3326229.3326248>.

Christina Katsamaki, Fabrice Rouillier, Elias P. Tsigaridas, Zafeirakis Zafeirakopoulos. On the geometry and the topology of parametric curves. ISSAC 2020 - International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, July 20-23, 2020, 10.1145/3373207.3404062 Christina Katsamaki, Fabrice Rouillier, Elias P. Tsigaridas, Zafeirakis Zafeirakopoulos. PTOPO: a maple package for the topology of parametric curves. ACM Commun. Comput. Algebra, 2020, 10.1145/3427218.3427223