Sparse FGLM algorithms

作     者：Faugere, Jean-Charles Mou, Chenqi 

作者机构：Sorbonne Univ UPMC Univ Paris 06 CNRS INRIAEquipe PolSysLIP6 4 Pl Jussieu F-75005 Paris France Beihang Univ LMIB Sch Math & Syst Sci Beijing 100191 Peoples R China 

出 版 物：《JOURNAL OF SYMBOLIC COMPUTATION》 (符号计算杂志)

年 卷 期：2017年第80卷第Part3期

页      面：538-569页

核心收录：

学科分类：08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：HPAC grant of the French National Research Agency [HPAC ANR-11-BS02-013] National Natural Science Foundation of China [NSFC 11401018] ECCA project of the Sino-French Laboratory for Computer Science, Automation and Applied Mathematics 

主　　题：Grobner bases Change of ordering Zero-dimensional ideal Sparse matrix Wiedemann algorithm BMS algorithm 

摘      要：Given a zero-dimensional ideal I subset of K([x(1), ..., x(n)] 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 FGLM algorithm. Combining 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 60000. 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(N-1 +n log(D)(2))), where N1 is the number of nonzero entries of a multiplication matrix;the other is deterministic and computes the LEX Grinner basis of 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 multidimensional 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 that its construction is free. With the asymptotic analysis of such sparsity, we are able to show that for generic systems the complexity above becomes O (root 6/n pi D2+n-1/n). (C) 2016 Elsevier Ltd. All rights reserved.