Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T04:12:22.052Z Has data issue: false hasContentIssue false
  • English
  • Français

An extension of Buchberger’s criteria for Gröbner basis decision

Part of: Computational aspects and applications

Published online by Cambridge University Press:  01 May 2010

John Perry
John Perry*
Affiliation:
Department of Mathematics, The University of Southern Mississippi, 118 College Drive, Box #5045 Hattiesburg, MS 39406, USA (email: [email protected])

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Two fundamental questions in the theory of Gröbner bases are decision (‘Is a basis G of a polynomial ideal a Gröbner basis?’) and transformation (‘If it is not, how do we transform it into a Gröbner basis?’) This paper considers the first question. It is well known that G is a Gröbner basis if and only if a certain set of polynomials (the S-polynomials) satisfy a certain property. In general there are m(m−1)/2 of these, where m is the number of polynomials in G, but criteria due to Buchberger and others often allow one to consider a smaller number. This paper presents two original results. The first is a new characterization theorem for Gröbner bases that makes use of a new criterion that extends Buchberger’s criteria. The second is the identification of a class of polynomial systems G for which the new criterion has dramatic impact, reducing the worst-case scenario from m(m−1)/2 S-polynomials to m−1.

MSC classification

Secondary: 13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 13 , January 2010 , pp. 111 - 129
Copyright
Copyright © London Mathematical Society 2010

References

[1] Adams, W. and Loustaunau, P., An introduction to Gröbner bases, Graduate Studies in Mathematics 3 (American Mathematical Society, Providence, RI, 1994).Google Scholar
[2] Backelin, J. and Fröberg, R., ‘How we proved that there are exactly 924 cyclic-7 roots’, ISSAC ’91: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ACM Press, New York, NY, 1991) 103–111, ISBN:0-89791-437-6.Google Scholar
[3] Becker, T., Weispfenning, V. and Kredel, H., Gröbner bases: a computational approach to commutative algebra (Springer, New York, 1993).Google Scholar
[4] Buchberger, B., ‘Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalem Polynomideal (an algorithm for finding the basis elements in the residue class ring modulo a zero dimensional polynomial ideal)’. PhD Thesis, Mathematical Institute, University of Innsbruck, Austria, 1965. English translation published in J. Symbolic Comput. 41 (2006) 475–511.Google Scholar
[5] Buchberger, B., ‘An algorithmic criterion for the solvability of a system of algebraic equations’, Aequationes Math. 4 (1970) 374–383 Gröbner Bases and Applications, London Mathematical Society Lecture Note Series 251 (1998) (English translation).Google Scholar
[6] Buchberger, B., ‘A criterion for detecting unnecessary reductions in the construction of Gröbner bases’, Proceedings of the EUROSAM 79 Symposium on Symbolic and Algebraic Manipulation, Marseille, 26–28 June 1979, Lecture Notes in Computer Science 72 (ed. Ng, E. W.; Springer, Berlin, 1979) 3–21.Google Scholar
[7] Buchberger, B., ‘Gröbner-bases: an algorithmic method in polynomial ideal theory’, Multidimensional systems theory — progress, directions and open problems in multidimensional systems, (ed. Bose, N. K.; Reidel, Dordrecht, 1985) 184–232.Google Scholar
[8] Caboara, M., Kreuzer, M. and Robbiano, L., ‘Minimal sets of critical pairs’, Proceedings of the First Congress of Mathematical Software, (eds Cohen, B., Gao, X. and Takayama, N.; World Scientific, Singapore, 2002) 390–404.Google Scholar
[9] Cohen, A. M., Cuypers, H. and Sterk, H. (eds) Some tapas of computer algebra, Algorithms and Computation in Mathematics 4 (Springer, Berlin, 1999).Google Scholar
[10] Cox, D., Little, J. and O’Shea, D., Ideals, varieties, and algorithms, 2nd edn (Springer, New York, 1997).Google Scholar
[11] Cox, D., Little, J. and O’Shea, D., Using algebraic geometry (Springer, New York, 1998).Google Scholar
[12] Gebauer, R. and Möller, H., ‘On an installation of Buchberger’s algorithm’, J. Symbolic Comput. 6 (1988) 275–286.Google Scholar
[13] Hong, H. and Perry, J., ‘Are Buchberger’s criteria necessary for the chain condition?’, J. Symbolic Comput. 42 (2007) 717–732.Google Scholar
[14] Jacobi, C. G. J., ‘De binis quibuslibet functionibus homogeneis secundi ordinis per substitutiones lineares in alias binas transformandis, quae solis quadratis variabilium constant; una cum variis theorematis de transformatione et determinatione integralium multiplicium’, J. Reine Angew. Math. 12 (1833) 1–69.Google Scholar
[15] Kollreider, C. and Buchberger, B., ‘An improved algorithmic construction of Gröbner-bases for polynomial ideals’, ACM SIGSAM Bull. 12 (1978) 27–36.Google Scholar
[16] Kreuzer, M. and Robbiano, L., Computational commutative algebra I (Springer, Heidelberg, 2000).Google Scholar
[17] Lazard, D., ‘Gröbner bases, Gaussian elimination, and resolution of systems of algebraic equations’, EUROCAL ’83, European Computer Algebra Conference, Lecture Notes in Computer Science 162 (ed. van Hulzen, J. A.; Springer, Berlin, 1983) 146–156.Google Scholar
[18] Möller, H., Mora, F. and Traverso, C., ‘Gröbner bases computation using syzygies’, Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery (ed. Wang, P. S.; ACM Press, New York, NY, 1992) 320–328.Google Scholar
[19] Rice, A. and Torrence, E., ‘Shutting up like a telescope: Lewis Carroll’s curious condensation method for evaluating determinants’, College Math. J. 38 (2007) 85–95.Google Scholar