Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity

Jean-Charles Faugère 1 Mohab Safey El Din 1 Pierre-Jean Spaenlehauer 2, 1
1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
2 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Solving multihomogeneous systems, as a wide range of \emph{structured algebraic systems} occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Gröbner bases algorithms seems to be easier than solving homogeneous systems of the same degree. Nevertheless, the reasons of this behaviour are not clear. In this paper, we focus on bilinear systems (i.e. bihomogeneous systems where all equations have bidegree $(1,1)$). Our goal is to provide a theoretical explanation of the aforementioned experimental behaviour and to propose new techniques to speed up the Gröbner basis computations by using the multihomogeneous structure of those systems. The contributions are theoretical and practical. First, we adapt the classical $F_5$ criterion to avoid reductions to zero which occur when the input is a set of bilinear polynomials. We also prove an explicit form of the Hilbert series of bihomogeneous ideals generated by generic bilinear polynomials and give a new upper bound on the degree of regularity of generic affine bilinear systems. We propose also a variant of the $F_5$ Algorithm dedicated to multihomogeneous systems which exploits a structural property of the Macaulay matrix which occurs on such inputs. Experimental results show that this variant requires less time and memory than the classical homogeneous $F_5$ Algorithm. Lastly, we investigate the complexity of computing a Gröbner basis for the grevlex ordering of a generic $0$-dimensional affine bilinear system over $k[x_1,\ldots, x_{n_x}, y_1,\ldots, y_{n_y}]$. In particular, we show that this complexity is upper bounded by $O\left({{n_x+n_y+\min(n_x+1,n_y+1)}\choose{\min(n_x+1,n_y+1)}}^\omega\right)$, which is polynomial in $n_x+n_y$ (i.e. the number of unknowns) when $\min(n_x,n_y)$ is constant.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2011, 46 (4), pp.406-437. <10.1016/j.jsc.2010.10.014>
Liste complète des métadonnées


https://hal.inria.fr/inria-00596631
Contributeur : Jean-Charles Faugere <>
Soumis le : lundi 30 mai 2011 - 13:32:27
Dernière modification le : lundi 29 mai 2017 - 14:26:16
Document(s) archivé(s) le : vendredi 9 novembre 2012 - 13:55:25

Fichier

JSC_FSS10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer. Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity. Journal of Symbolic Computation, Elsevier, 2011, 46 (4), pp.406-437. <10.1016/j.jsc.2010.10.014>. <inria-00596631>

Partager

Métriques

Consultations de
la notice

281

Téléchargements du document

103