Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
Résumé
Let I in K[x1,...,xn] be a 0-dimensional ideal of degree D where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Gröbner bases of I is crucial in polynomial system solving. Through the algorithm FGLM, this task is classically tackled by linear algebra operations in K[x1,...,xn]/I. With recent progress on Gröbner bases computations, this step turns out to be the bottleneck of the whole solving process. Our contribution is an algorithm that takes advantage of the sparsity structure of multiplication matrices appearing during the change of ordering. This sparsity structure arises even when the input polynomial system defining I is dense. As a by-product, we obtain an implementation which is able to manipulate 0-dimensional ideals over a prime field of degree greater than 30000. It outperforms the Magma/Singular/FGb implementations of FGLM. First, we investigate the particular but important shape position case. The obtained algorithm performs the change of ordering within a complexity O(D(N1+nlog(D))), where N1 is the number of nonzero entries of a multiplication matrix. This almost matches the complexity of computing the minimal polynomial of one multiplication matrix. Then, we address the general case and give corresponding complexity results. Our algorithm is dynamic in the sense that it selects automatically which strategy to use depending on the input. Its key ingredients are the Wiedemann algorithm to handle 1-dimensional linear recurrence (for the shape position case), and the Berlekamp-Massey-Sakata algorithm from Coding Theory to handle multi-dimensional linearly recurring sequences in the general case.