Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Journal of Algebra Année : 2022

Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems

Jérémy Berthomieu
Andrew Ferguson
  • Fonction : Auteur
  • PersonId : 1076496
Mohab Safey El Din

Résumé

Determinantal polynomial systems are those involving maximal minors of some given matrix. An important situation where these arise is the computation of the critical values of a polynomial map restricted to an algebraic set. This leads directly to a strategy for, among other problems, polynomial optimisation. Computing Gröbner bases is a classical method for solving polynomial systems in general. For practical computations, this consists of two main stages. First, a Gröbner basis is computed with respect to a DRL (degree reverse lexicographic) ordering. Then, a change of ordering algorithm, such as \textsf{Sparse-FGLM}, designed by Faug\`ere and Mou, is used to find a Gröbner basis of the same system but with respect to a lexicographic ordering. The complexity of this latter step, in terms of the number of arithmetic operations in the ground field, is $O(mD^2)$, where $D$ is the degree of the ideal generated by the input and $m$ is the number of non-trivial columns of a certain $D \times D$ matrix. While asymptotic estimates are known for $m$ in the case of \textit{generic} polynomial systems, thus far, the complexity of \textsf{Sparse-FGLM} was unknown for the class of determinantal systems. By assuming Fröberg's conjecture, thus ensuring that the Hilbert series of generic determinantal ideals have the necessary structure, we expand the work of Moreno-Soc\'ias by detailing the structure of the DRL staircase in the determinantal setting. Then we study the asymptotics of the quantity $m$ by relating it to the coefficients of these Hilbert series. Consequently, we arrive at a new bound on the complexity of the \textsf{Sparse-FGLM} algorithm for generic determinantal systems and, in particular, for generic critical point systems. We consider the ideal inside the polynomial ring $\mathbb{K}[x_1, \dots, x_n]$, where $\mathbb{K}$ is some infinite field, generated by $p$ generic polynomials of degree $d$ and the maximal minors of a $p \times (n-1)$ polynomial matrix with generic entries of degree $d-1$. Then, in this setting, for the case $d=2$ and for $n \gg p$ we establish an exact formula for $m$ in terms of $n$ and $p$. Moreover, for $d \geq 3$, we give a tight asymptotic formula, as $n \to \infty$, for $m$ in terms of $n,p$ and $d$.
Fichier principal
Vignette du fichier
CombDetv2.pdf (1.11 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03214157 , version 1 (30-04-2021)
hal-03214157 , version 2 (18-03-2022)

Identifiants

Citer

Jérémy Berthomieu, Alin Bostan, Andrew Ferguson, Mohab Safey El Din. Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems. Journal of Algebra, 2022, 602, pp.154-180. ⟨10.1016/j.jalgebra.2022.03.002⟩. ⟨hal-03214157v2⟩
381 Consultations
236 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More