一种改进的计算Fx,y上理想的Gr(o)bner基算法

摘要

利用Buchberger第二准则证明了当单项式序为字典序时,多项式组G经过约化和多项式排序后,如果其中相邻元素之间的S-多项式被G除得的余式都为零,那么G就是理想的Gr(o)bner基.同时,当理想的单项式序为分次逆字典序时是最容易计算出其Gr(o)bner基.改进的算法利用这两个单项式序的优点,通过在计算过程中改变单项式序,使得S-多项式的计算次数大幅减少,最终正确有效地计算出F[x,y]上理想的Gr(o)bner基.最后随机选取了几组多项式,与著名的F4算法进行对比.实验结果显示,改进算法比F4算法更快,甚至快上一个数量级,而且可以求解出相关算法不能求解的案例.