Gröbner Bases of Ideals Invariant under a Commutative Group: the Non-Modular Case

Jean-Charles Faugère 1 Jules Svartz 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We propose efficient algorithms to compute the Gröbner basis of an ideal $I\subset k[x_1,\dots,x_n]$ globally invariant under the action of a commutative matrix group $G$, in the non-modular case (where $char(k)$ doesn't divide $|G|$). The idea is to simultaneously diagonalize the matrices in $G$, and apply a linear change of variables on $I$ corresponding to the base-change matrix of this diagonalization. We can now suppose that the matrices acting on $I$ are diagonal. This action induces a grading on the ring $R=k[x_1,\dots,x_n]$, compatible with the degree, indexed by a group related to $G$, that we call $G$-degree. The next step is the observation that this grading is maintained during a Gröbner basis computation or even a change of ordering, which allows us to split the Macaulay matrices into $|G|$ submatrices of roughly the same size. In the same way, we are able to split the canonical basis of $R/I$ (the staircase) if $I$ is a zero-dimensional ideal. Therefore, we derive \emph{abelian} versions of the classical algorithms $F_4$, $F_5$ or FGLM. Moreover, this new variant of $F_4/F_5$ allows complete parallelization of the linear algebra steps, which has been successfully implemented. On instances coming from applications (NTRU crypto-system or the Cyclic-n problem), a speed-up of more than 400 can be obtained. For example, a Gröbner basis of the Cyclic-11 problem can be solved in less than 8 hours with this variant of $F_4$. Moreover, using this method, we can identify new classes of polynomial systems that can be solved in polynomial time.
Type de document :
Communication dans un congrès
The 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, Jun 2013, Boston, United States. ACM, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, pp.347-354, 2013, <10.1145/2465506.2465944>
Liste complète des métadonnées

https://hal.inria.fr/hal-00819337
Contributeur : Jules Svartz <>
Soumis le : mardi 30 avril 2013 - 18:15:59
Dernière modification le : mardi 9 août 2016 - 11:28:10
Document(s) archivé(s) le : mercredi 31 juillet 2013 - 05:00:08

Fichiers

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

Identifiants

Collections

Citation

Jean-Charles Faugère, Jules Svartz. Gröbner Bases of Ideals Invariant under a Commutative Group: the Non-Modular Case. The 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, Jun 2013, Boston, United States. ACM, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, pp.347-354, 2013, <10.1145/2465506.2465944>. <hal-00819337>

Partager

Métriques

Consultations de
la notice

323

Téléchargements du document

291