不变理想的Gr(o)bner基提升算法

摘要

采用Gr(o)bner基方法,可以把一个在有限群作用下不变的多项式写成不变环的生成元的多项式.核心问题是如何有效地计算这个正维不变理想的Gr(o)bner基.本文引入一个有效提升算法来计算这组Gr(o)bner基.当用straight line program模型对整个计算过程进行复杂度分析时,可以把计算开销控制在多项式时间内.%A polynomial invariant under the action of a finite group can be rewritten into generators of therninvariant ring by Gr(o)bner basis method. The key question is how to find an efficient way to compute thernGrobner basis of the invariant ideal which is positive dimensional. We introduce a lifting algorithm for thisrncomputation process. If we use straight line program to analyze the complexity result, this process can berndone within polynomial time.