Sub-cubic Change of Ordering for Gröner Basis: A Probabilistic Approach

Jean-Charles Faugère 1 Pierrick Gaudry 2 Louise Huot 1 Guénaël Renault 1
1 PolSys - Polynomial Systems
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 : The usual algorithm to solve polynomial systems using Gröbner bases consists of two steps: first computing the DRL Gröbner basis using the F5 algorithm then computing the LEX Gröbner basis using a change of ordering algorithm. When the Bézout bound is reached, the bottleneck of the total solving process is the change of ordering step. For 20 years, thanks to the FGLM algorithm the complexity of change of ordering is known to be cubic in the number of solutions of the system to solve. We show that, in the generic case or up to a generic linear change of variables, the multiplicative structure of the quotient ring can be computed with no arithmetic operation. Moreover, given this multiplicative structure we propose a change of ordering algorithm for Shape Position ideals whose complexity is polynomial in the number of solutions with exponent ω where 2 ≤ ω < 2.3727 is the exponent in the complexity of multiplying two dense matrices. As a consequence, we propose a new Las Vegas algorithm for solving polynomial systems with a finite number of solutions by using Gröbner basis for which the change of ordering step has a sub-cubic (i.e. with exponent ω) complexity and whose total complexity is dominated by the complexity of the F5 algorithm. In practice we obtain significant speedups for various polynomial systems by a factor up to 1500 for specific cases and we are now able to tackle some instances that were intractable.
Type de document :
Communication dans un congrès
ISSAC '14 - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. ACM, ISSAC '14 - Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp.170--177, 2014, 〈10.1145/2608628.2608669〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01064551
Contributeur : Jean-Charles Faugère <>
Soumis le : mardi 16 septembre 2014 - 15:41:52
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : mercredi 17 décembre 2014 - 11:25:47

Fichier

p170-faugere.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | UPMC | LIP6 | UNIV-LORRAINE | LORIA-ALGO | LORIA | INRIA-ROCQ

Citation

Jean-Charles Faugère, Pierrick Gaudry, Louise Huot, Guénaël Renault. Sub-cubic Change of Ordering for Gröner Basis: A Probabilistic Approach. ISSAC '14 - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. ACM, ISSAC '14 - Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp.170--177, 2014, 〈10.1145/2608628.2608669〉. 〈hal-01064551〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

623

Téléchargements de fichiers

273

Contact


archive-ouverte@inria.fr