Journal of University of Chinese Academy of Sciences >
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
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
WU Jie , CHEN Yu-Fu . Lifting algorithms for Gröbner basis computation of invariant ideals[J]. Journal of University of Chinese Academy of Sciences, 2009 , 26(6) : 731 -744 . DOI: 10.7523/j.issn.2095-6134.2009.6.002
[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.
/
| 〈 |
|
〉 |