| 布尔环上的分支Gr(o)bner基算法 |
| |
| 引用本文： | 孙瑶,王定康.布尔环上的分支Gr(o)bner基算法[J].系统科学与数学,2009,29(9):1266-1277. |
| |
| 作者姓名： | 孙瑶 王定康 |
| |
| 作者单位： | 中国科学院数学与系统科学研究院数学机械化重点实验室,北京,100190 |
| |
| 摘 要： | 众所周知Gr\"obner基在很多领域都有着十分重要的应用.近些年来Gr\"obner基算法有了很大的改进,其中最著名的是Faug\`ere提出的F4和F5算法. 这两个算法具有很高的效率但通常需要消耗大量的内存.鉴于此,将给出一个布尔环上基于zdd数据结构的分支Gr\"obner基算法,该算法不仅可以大大降低对内存的消耗,还能有效的控制矩阵规模,从而提高算法的整体效率.详细阐述并证明了算法的基本理论,介绍该分支算法的数据结构及分支策略.最后通过实验数据可以发现,在很多例子中此算法都要优于Magma中的F4算法.
|
| 关 键 词： | 分支Gr\"obner基 布尔环 zdd数据结构. |
| 收稿时间： | 2009-7-30 |
BRANCH GR(O)BNER BASES ALGORITHM OVER BOOLEAN RING |
| |
| SUN Yao,WANG Dingkang.BRANCH GR(O)BNER BASES ALGORITHM OVER BOOLEAN RING[J].Journal of Systems Science and Mathematical Sciences,2009,29(9):1266-1277. |
| |
| Authors: | SUN Yao WANG Dingkang |
| |
| Affiliation: | Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190 |
| |
| Abstract: | It is well known that Gr\"obner bases have extensive applications in many fields.In the recent years, many improvements have been made for the Gr\"obner algorithm,the most famous of which are the F4 and F5 algorithm introduced by Faug\`ere.Although both of the two algorithms have excellent efficiency,they need enormous memories during the computation. So we will present a new branch Gr\"obner bases algorithm based on the zdd data structure overthe 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. |
| |
| Keywords: | Branch Gr\"obner bases boolean ring zdd data structure |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
|
点击此处可从《系统科学与数学》下载全文 |
|
