一种Gr?bner基的改进算法

作     者：赵向东 

作者单位：天津职业技术师范大学 

学位级别：硕士

导师姓名：孙维昆

授予年度：2020年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：Gr?bner基 准则对 选择策略 GR?BNERNEW2算法 GR?BNERNEW2C算法 

摘      要：Gr?bner基的理论基础与算法研究在计算代数几何、几何定理的机器证明、机器人学、代数编码理论、密码学、图论等领域扮演着重要的角色,且Buchberger算法是Gr?bner基的核心,但Buchberger算法在求解理想的Gr?bner基方面时,计算效率低、存在冗余计算,因而诸多学者从多个方向对如何提高此算法计算效率进行了深入研究,并提出了许多新的算法,其中最有效的诸如:F4算法、G2V算法、GVW算法等。本文通过研究分析Gr?bner基算法——GR?BNERNEW2算法以及F4算法,并借助Maple平台实例测试发现,GR?BNERNEW2算法在计算Cyclic5,Cyclic6,Gerdt 1、2、3,Katsura-5等变元较多的标准多项式理想集的Gr?bner基时,计算效率不高,程序执行时间较长的问题,因此,在GR?BNERNEW2算法基础之上,增加了一种选择策略——即基于对的首单项式的最小公倍式次数最低来选择准则对,构建了一种改进的Gr?bner基算法—GR?BNERNEW2C算法,给出了GR?BNERNEW2C算法正确性和终止性的证明,以保证GR?BNERNEW2C算法的完整性。改进的GR?BNERNEW2C算法在计算变元个数较多的多项式理想的Gr?bner基时,避免了计算效率低,程序运行时间较长的问题,提高了Gr?bner基的计算效率。进一步,在Maple环境下实现了GR?BNERNEW2C算法、GR?BNERNEW2算法、F4算法以及Buchberger算法,并通过具体实例对比分析了GR?BNERNEW2C算法、F4算法、GR?BNERNEW2算法、Buchberger算法在求解Cyclic5、6,Gerdt 1、2、3,Katsura-6、7,Haas3、Eco7、Noon6等系统时的计算时间。最后,本文将改进的GR?BNERNEW2C算法应用于多项式方程组求解、附加关系化简问题、判定理想成员问题,为进一步研究Gr?bner基算法,促进各个学科领域发展奠定一定的基础。