Finer Complexity Estimates for the Change of Ordering of Gröbner Bases for Generic Symmetric Determinantal Ideals - Sorbonne Université
Conference Papers Year : 2022

Finer Complexity Estimates for the Change of Ordering of Gröbner Bases for Generic Symmetric Determinantal Ideals

Andrew Ferguson
  • Function : Author
  • PersonId : 1076496
Huu Phuoc Le

Abstract

Polynomial matrices and ideals generated by their minors appear in various domains such as cryptography, polynomial optimization and effective algebraic geometry. When the given matrix is symmetric, this additional structure on top of the determinantal structure, affects computations on the derived ideals. Thus, understanding the complexity of these computations is important. Moreover, this study serves as a stepping stone towards further understanding the effects of structure in determinantal systems, such as those coming from moment matrices. In this paper, we focus on the Sparse-FGLM algorithm, the state-of-the-art for changing ordering of Gröbner bases of zero-dimensional ideals. Under a variant of Fröberg’s conjecture, we study its complexity for symmetric determinantal ideals and identify the gain of exploiting sparsity in the Sparse-FGLM algorithm compared with the classical FGLM algorithm. For an $n \times n$ symmetric matrix with polynomial entries of degree $d$, we show that the complexity of Sparse-FGLM for zero-dimensional determinantal ideals obtained from this matrix over that of the FGLM algorithm is at least $O(1/d)$. Moreover, for some specific sizes of minors, we prove finer results of at least $O(1/nd)$ and $O(1/n^3d)$.
Fichier principal
Vignette du fichier
symdet.pdf (780.11 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03573833 , version 1 (14-02-2022)
hal-03573833 , version 2 (01-06-2022)

Identifiers

Cite

Andrew Ferguson, Huu Phuoc Le. Finer Complexity Estimates for the Change of Ordering of Gröbner Bases for Generic Symmetric Determinantal Ideals. International Symposium on Symbolic and Algebraic Computation (ISSAC '22), Jul 2022, Villeneuve-d'Ascq, France. pp.9, ⟨10.1145/3476446.3536182⟩. ⟨hal-03573833v2⟩
227 View
178 Download

Altmetric

Share

More