Algorithm for efficiently computing a Groebner basis with high probability

我们发现，通过中国剩余定理组合模Groebner基来计算有理数上的Groebner基的过程中，通过将所有相同次数的多项式转换在一起可以减少整数-有理数转换的代价。为了证明Groebner基候选的正确性，我们开发了一个算法来计算候选中每个元素的精确生成关系。我们首先计算有限域上的生成关系。然后用变量代替系数，得到一个庞大的线性方程组。利用在有限域上求解该系统所得到的信息，我们可以减小系统的规模，使解是唯一的。然后我们就可以利用Hensel提升来求解该系统，从而可以有效地求解该系统。

We found that the cost of integer-rational number conversion in the procedure forcomputing Groebner bases over the rationals by combining modular Groebner bases by Chinese remainder theorem can be reduced by converting all the polynomials with the same degree together.In order to show the correctness of a Groebner basis candidate, we developed an algorithm which computes an exact generating relation for each element in the candidate. We first compute a generating relation over a finite field. Then we replace the coefficients with variables to obtain a huge system of linear equations. By using the information obtained by solving the system over the finite field, we can reduce the size of the system and the solution is made unique. Then we can apply Hensel lifting for solving the system and we can efficiently solve the system.