*晨琪 牟 (北京航空航天大学数学与系统科学学院)
Groebner basis is an important tool in computational ideal theory, and the term ordering plays an important role in the theory of Groebner bases. In particular, the common strategy to solve a polynomial system is to first compute the basis of the ideal defined by the system w.r.t. DRL, change its ordering to LEX, and perhaps further convert the LEX Groebner basis to triangular sets. Given a zero-dimensional ideal $I \subset \mathbb{K}[x_1,\ldots,x_n]$ of degree $D$, the transformation of the ordering of its Groebner basis from DRL to LEX 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. In this talk we present 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 $N_1$ is the number of nonzero entries of a multiplication matrix; the other is deterministic and computes the LEX Groebner 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 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(\sqrt{6/n \pi}D^{2+\frac{n-1}{n}})$. This talk is based on joint work with Jean-Charles Faugere.
Math formula preview: