摘要
众所周知Grbner基在很多领域都有着十分重要的应用.近些年来Grbner基算法有了很大的改进,其中最著名的是Faugère提出的F4和F5算法.这两个算法具有很高的效率但通常需要消耗大量的内存.鉴于此,将给出一个布尔环上基于zdd数据结构的分支Grbner基算法,该算法不仅可以大大降低对内存的消耗,还能有效的控制矩阵规模,从而提高算法的整体效率.详细阐述并证明了算法的基本理论,介绍该分支算法的数据结构及分支策略.最后通过实验数据可以发现,在很多例子中此算法都要优于Magma中的F4算法.
It is well known that Groebner bases have extensive applications in many fields. In the recent years, many improvements have been made for the Groebner algorithm, the most famous of which are the F4 and F5 algorithm introduced by Faugere. Although both of the two algorithms have excellent efficiency, they need enormous memories during the computation. So we will present a new branch Groebner bases algorithm based on the zdd data structure over the boolean ring. This new algorithm not only lowers the usage of memories but also constrains the matrix generated in the computation within a reasonable size. In this paper, we will detail the theory and the proof of this basic algorithm and introduce the zdd data strucure and the branch strategy as well. For many cases, its implementation in Linux is superior to the F4 algorithm implemented by Steel in Magma.
出处
《系统科学与数学》
CSCD
北大核心
2009年第9期1266-1277,共12页
Journal of Systems Science and Mathematical Sciences
基金
国家自然科学基金(NSFC60821002/F02,10771206)资助
