Lifting algorithms for Gröbner basis computation of invariant ideals
Received date: 2009-04-07
Revised date: 2009-05-11
Online published: 2009-11-15
采用Gröbner基方法,可以把一个在有限群作用下不变的多项式写成不变环的生成元的多项式.核心问题是如何有效地计算这个正维不变理想的Gröbner基.本文引入一个有效提升算法来计算这组Gröbner基.当用straight line program模型对整个计算过程进行复杂度分析时,可以把计算开销控制在多项式时间内.
关键词： Grö; bner基; 提升; 不变性理论; straight line program
吴杰 , 陈玉福 . 不变理想的Gröbner基提升算法[J]. 中国科学院大学学报, 2009 , 26(6) : 731 -744 . DOI: 10.7523/j.issn.2095-6134.2009.6.002
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
[1] Buchberger B. Grbner bases: An algorithmic method in polynomial ideal theory //Multidimensional System Theory. Dordrecht: Bose N K, Reidel D Publishing Company, 1985.
[2] Dahan X, Schost E, Wu J. Evaluation properties of invariant polynomials
[J]. Journal of Symbolic Computation, 2009,44(11):1592-1604.
[3] Gaudry P, Schost E, Thiery N. Evaluation properties of symmetric polynomials
[J]. Internat J Algebra Comput, 2006, 16(3): 505-523.
[4] Cox D, Little J, O’shea D. Ideals, varieties and algorithms . 2nd edition. Springer-Verlag, 1996.
[5] Derksen H, Kemper G. Computational Invariant Theory //Volume 130 of Encyclopaedia of Mathematical Sciences. Springer Verlag, 2002.
[6] Arnold E A. Modular algorithms for computing Grbner bases
[J]. Journal of Symbolic Computation, 2003, 35: 403-419.
[7] Schost E. Complexity results for triangular sets
[J]. Journal of Symbolic Computation, 2003, 36(3-4): 555-594.
[8] Faugere J C, Gianni P, Lazard D, et al. Efficient computation of zero-dimensional Grbner bases by change of ordering
[J]. Journal of Symbolic Computation, 1993, 16(4):329-344.
[9] Sturmfels B. Algorithms in invariant theory //Texts and Monographs in Symbolic Computation. Springer-Verlag, 1993.
[10] Hong H. Groebner basis under composition Ⅱ //International Conference on Symbolic and Algebraic Computation. 1996.
[11] Schost E. Computing parametric geometric resolutions
[J]. Applicable Algebra in Engineering, Communication and Computing, 2003, 13(5): 349-393.
[12] Cox D, Little J, O’shea D. Using algebraic geometry
[M]. New York-Berlin-Heidelberg: Springer-Verlag, 1997.
[13] von zur Gathen J, Gerhard J. Modern computer algebra
[M]. Cambridge University Press, 1999.
[14] Kaltofen E. Greatest common divisors of polynomials given by straight-line programs
[J]. J ACM, 1988,35(1):231-264.
[15] Giusti M, Lecerf G, Salvy B. A Grbner free alternative for polynomial system sloving
[J]. J Complexity, 2001,17(2):154-211.
/
| 〈 |
|
〉 |
