A NEW FRAMEWORK FOR COMPUTING GROBNER BASES

作者:Gao, Shuhong*; Volny, Frank; Wang, Mingsheng
来源:Mathematics of Computation, 2015, 85(297): 449-465.
DOI:10.1090/mcom/2969

摘要

This paper presents a new framework for computing Grobner bases for ideals and syzygy modules. It is proposed to work in a module that accommodates any given ideal and the corresponding syzygy module (for the given generators of the ideal). A strong Grobner basis for this module contains Grobner bases for both the ideal and the syzygy module. The main result is a simple characterization of strong Grobner bases. This characterization can detect useless S-polynomials without reductions, thus yields an efficient algorithm. It also explains all the rewritten rules used in F5 and the recent papers in the literature. Rigorous proofs are given for the correctness and finite termination of the algorithm. For any term order for an ideal, one may vary signature orders (i.e. the term orders for the syzygy module). It is shown by computer experiments on benchmark examples that signature orders based on weighted terms are much better than other signature orders. This is useful for practical computation. Also, since computing Gobner bases for syzygies is a main computational task for free resolutions in commutative algebra, the algorithm of this paper should be useful for computing free resolutions in practice.

  • 出版日期2015-1
  • 单位中国科学院信息工程研究所