Uniform Gröbner bases for ideals generated by polynomials with parametric exponents

ABSTRACT

This paper presents a method for computing uniform Gröbner bases for certain ideals generated by polynomials with parametric exponents. The method proceeds by replacing monomials involving parametric exponents in the generators of an ideal with new variables, computing the reduced Gröbner basis for the resulting ideal with respect to a special monomial order, and then verifying whether the leading monomial ideal of the Gröbner basis satisfies some consistency conditions according to two criteria (of which one is derived from Buchberger graphs). When the consistency conditions are verified, a uniform Gröbner basis for the original ideal is obtained by substituting the new variables back to original monomials. The effectiveness and practical value of the method are demonstrated by its application to a family of ideals coming from the modeling of biological systems.

REFERENCES

• 1: Bayer, D., Galligo, A., Stillman, M.: Gröbner bases and extension of scalars. In: Computational Algebraic Geometry and Commutative Algebra (Eisenbud, D., Robbiano, L., eds.), pp. 198--215. Cambridge University Press, Cambridge, 1993.
• 2: Bruno Buchberger, A criterion for detecting unnecessary reductions in the construction of Groebner bases, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.3-21, June 01, 1979
• 3: Cinquin, O., Demongeot, J.: Positive and negative feedback: Striking a balance between necessary antagonists. J. Theor. Biol. 216: 229--241, 2002.
• 4: Cox, D., Little, J., O'Shea, D.: Ideals, Varieties and Algorithms. Springer, New York, 1992.
• 5: Cox, D., Little, J., O'Shea, D.: Using Algebraic Geometry. GTM 185. Springer, New York, 1998.
• 6: Diestel, R.: Graph Theory. Springer, New York, 1997.
• 7: Eisenbud, D.: Commutative Algebra. GTM 150. Springer, New York, 1994.
• 8: Hoon Hong, Groebner basis under composition II, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.79-85, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236906]
• 9: Michael Kalkbrener, On the stability of Groübner bases under specializations, Journal of Symbolic Computation, v.24 n.1, p.51-58, July 1997 [doi>10.1006/jsco.1997.0113 ]
• 10: Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra. GTM 227. Springer, New York, 2004.
• 11: Bhubaneswar Mishra, Algorithmic algebra, Springer-Verlag New York, Inc., New York, NY, 1993
• 12: Pan, W.: Uniform free resolutions of monomial ideals. Preprint (submitted for publication), University of Science and Technology of China, China, 2006.
• 13: Wang, D.: The projection property of regular systems and its application to solving parametric polynomial systems. In: Algorithmic Algebra and Logic (Passau, Germany, April 3-6, 2005), pp. 269--274. Herstellung und Verlag, Norderstedt, 2005.
• 14: Wang, D., Xia, B.: Algebraic analysis of stability for some biological systems. In: Algebraic Biology 2005 - Computer Algebra in Biology (Tokyo, Japan, November 28-30, 2005), pp. 75--83. Universal Academy Press, Inc., Tokyo, 2005.
• 15: Weispfenning, V.: Gröbner bases for binomials with parametric exponents. Preprint, Universität Passau, Germany, 2004.
• 16: Volker Weispfenning, Comprehensive Gro¨bner bases, Journal of Symbolic Computation, v.14 n.1, p.1-29, July 1992 [doi>10.1016/0747-7171(92)90023-W]
• 17: Kazuhiro Yokoyama, On systems of algebraic equations with parametric exponents, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.312-319, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005330]
• 18: Yokoyama, K.: On systems of algebraic equations with parametric exponents II. Presented at ACA 2005 (Nara, Japan, July 31 - August 3, 2005) and submitted for publication.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms

Keywords:
Buchberger graph, biological modeling, consistency condition, parametric exponent, polynomial ideal, uniform Gröbner basis