Sparse FGLM algorithms

Autor: Jean-Charles Faugère, Chenqi Mou
Přispěvatelé: Polynomial Systems (PolSys), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Rok vydání: 2017
Předmět:
FOS: Computer and information sciences
Computer Science - Symbolic Computation
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
010103 numerical & computational mathematics
Symbolic Computation (cs.SC)
01 natural sciences
Sparse matrix
Change of ordering
Combinatorics
Generic polynomial
Zero-dimensional ideals
Matrix (mathematics)
Gröbner basis
Wiedemann algorithm
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
0101 mathematics
Grobner bases
Chinese remainder theorem
Mathematics
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
Polynomial (hyperelastic model)
Discrete mathematics
Algebra and Number Theory
Degree (graph theory)
010102 general mathematics
Computational Mathematics
BMS algorithm
Multiplication
Algorithm
Zdroj: Journal of Symbolic Computation
Journal of Symbolic Computation, Elsevier, 2017, 80 (3), pp.538-569. ⟨10.1016/j.jsc.2016.07.025⟩
Journal of Symbolic Computation, 2017, 80 (3), pp.538-569. ⟨10.1016/j.jsc.2016.07.025⟩
ISSN: 0747-7171
1095-855X
DOI: 10.1016/j.jsc.2016.07.025
Popis: Given a zero-dimensional ideal I in K[x1,...,xn] of degree D, the transformation of the ordering of its Groebner 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 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 Magma and 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(N1+nlog(D))), where N1 is the number of nonzero entries of a multiplication matrix; the other is deterministic and computes the LEX Groebner basis of the radical of 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+(n-1)/n}})$.
Comment: 40 pages
Databáze: OpenAIRE
Externí odkaz: