Algorithm for efficiently computing a Groebner basis with high probability

点击翻译按钮获取中文摘要

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.