Sparse FGLM algorithms

Jean-Charles Faugère 1 Chenqi Mou 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : Given a zero-dimensional ideal $I \subset \kx$ of degree $D$, the transformation of the ordering of its \grobner basis from DRL to LEX is a key step in polynomial system solving and turns out to be the bottleneck of the whole solving process. Thus it is of crucial importance to design efficient algorithms to perform the change of ordering. The main contributions of this paper are several efficient methods for the change of ordering which take advantage of the sparsity of multiplication matrices in the classical {\sf FGLM} algorithm. Combing all these methods, we propose a deterministic top-level algorithm that automatically detects which method to use depending on the input. As a by-product, we have a fast implementation that is able to handle ideals of degree over $40000$. Such an implementation outperforms the {\sf Magma} and {\sf Singular} ones, as shown by our experiments. First for the shape position case, two methods are designed based on the Wiedemann algorithm: the first is probabilistic and its complexity to complete the change of ordering is $O(D(N_1+n\log (D)))$, where $N_1$ is the number of nonzero entries of a multiplication matrix; the other is deterministic and computes the LEX \grobner basis of $\sqrt{I}$ via Chinese Remainder Theorem. Then for the general case, the designed method is characterized by the Berlekamp--Massey--Sakata algorithm from Coding Theory to handle the multi-dimensional linearly recurring relations. Complexity analyses of all proposed methods are also provided. Furthermore, for generic polynomial systems, we present an explicit formula for the estimation of the sparsity of one main multiplication matrix, and prove its construction is free. With the asymptotic analysis of such sparsity, we are able to show for generic systems the complexity above becomes $O(\sqrt{6/n \pi} D^{2+\frac{n-1}{n}})$.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2017, 80 (3), pp.538 - 569. <10.1016/j.jsc.2016.07.025>
Liste complète des métadonnées

https://hal.inria.fr/hal-00807540
Contributeur : Jean-Charles Faugere <>
Soumis le : mercredi 3 avril 2013 - 17:37:37
Dernière modification le : mercredi 30 novembre 2016 - 11:45:02
Document(s) archivé(s) le : jeudi 4 juillet 2013 - 04:12:11

Fichier

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

Identifiants

Collections

Citation

Jean-Charles Faugère, Chenqi Mou. Sparse FGLM algorithms. Journal of Symbolic Computation, Elsevier, 2017, 80 (3), pp.538 - 569. <10.1016/j.jsc.2016.07.025>. <hal-00807540>

Partager

Métriques

Consultations de
la notice

521

Téléchargements du document

366