欢迎访问中国科学院大学学报,今天是

中国科学院大学学报 ›› 2009, Vol. 26 ›› Issue (6): 731-744.DOI: 10.7523/j.issn.2095-6134.2009.6.002

• 论文 • 上一篇    下一篇

不变理想的Gröbner基提升算法

吴杰, 陈玉福   

  1. 中国科学院研究生院数学科学学院,北京 100049
  • 收稿日期:2009-04-07 修回日期:2009-05-11 发布日期:2009-11-15
  • 通讯作者: 陈玉福

Lifting algorithms for Gröbner basis computation of invariant ideals

WU Jie, CHEN Yu-Fu   

  1. Graduate University of the Chinese Academy of Sciences, Beijing 100049, China
  • Received:2009-04-07 Revised:2009-05-11 Published:2009-11-15

摘要:

采用Gröbner基方法,可以把一个在有限群作用下不变的多项式写成不变环的生成元的多项式.核心问题是如何有效地计算这个正维不变理想的Gröbner基.本文引入一个有效提升算法来计算这组Gröbner基.当用straight line program模型对整个计算过程进行复杂度分析时,可以把计算开销控制在多项式时间内.

关键词: Grö, bner基, 提升, 不变性理论, straight line program

Abstract:

A polynomial invariant under the action of a finite group can be rewritten into generators of the invariant ring by Gröbner basis method. The key question is how to find an efficient way to compute the Gröbner basis of the invariant ideal which is positive dimensional. We introduce a lifting algorithm for this computation process. If we use straight line program to analyze the complexity result, this process can be done within polynomial time.

Key words: Gröbner basis, lifting, invariant theory, straight line program

中图分类号: