×

zbMATH — the first resource for mathematics

Computing inhomogeneous Gröbner bases. (English) Zbl 1252.13018
Summary: We describe how an idea centered on the concept of self-saturation allows several improvements in the computation of Gröbner bases via Buchberger’s Algorithm. In a nutshell, the idea is to extend the advantages of computing with homogeneous polynomials or vectors to the general case. When the input data are not homogeneous, we use as a main tool the procedure of a self-saturating Buchberger’s Algorithm. Another strictly related topic is treated later when a mathematical foundation is given to the sugar trick which is nowadays widely used in most of the implementations of Buchberger’s Algorithm. A special emphasis is also given to the case of a single grading, and subsequently some timings and indicators showing the practical merits of our approach.

MSC:
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13-04 Software, source code, etc. for problems pertaining to commutative algebra
Software:
CoCoA; slimgb
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bigatti, A.; La Scala, R.; Robbiano, L., Computing toric ideals, J. symbolic comput., 27, 351-365, (1999) · Zbl 0958.13009
[2] Brickenstein, M., 2006. Slimgb: Gröbner bases with slim polynomials. In: Rhine Workshop on Computer Algebra. Proceedings of RWCA’06, Basel, March 2006. pp. 55-66.
[3] Buchberger, B., 1965. Ein algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal, Ph.D. Thesis, Universität Innsbruck, English version in J. Symbolic Comput. 41 (2006) 475-511.
[4] Buchberger, B., A criterion for detecting unnecessary reductions in the construction of Groebner bases, (), 3-21
[5] Buchberger, B., Groebner bases: an algorithmic method in polynomial ideal theory, (), 184-232
[6] Caboara, M., De Dominicis, G., Robbiano, L., 1996. Multigraded Hilbert functions and Buchberger algorithm. In: Proc. of the ISSAC’96. pp. 72-85. · Zbl 0928.13018
[7] Caboara, M.; Kreuzer, M.; Robbiano, L., Efficiently computing minimal sets of critical pairs, J. symbolic. comput., 38, 1169-1190, (2004) · Zbl 1137.13315
[8] The CoCoATeam, CoCoA: a system for doing Computations in Commutative Algebra, available at http://cocoa.dima.unige.it.
[9] Faugère, J.C., A new efficient algorithm for computing Gröbner bases (F4), J. pure appl. algebra, 139, 61-88, (1999) · Zbl 0930.68174
[10] Faugère, J.C., A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), (), 75-83 · Zbl 1072.68664
[11] Gebauer, R.; Möller, H.M., On an installation of buchberger’s algorithm, J. symbolic comput., 6, 257-286, (1987) · Zbl 0675.13013
[12] Giovini, A.; Mora, T.; Niesi, G.; Robbiano, L.; Traverso, C., One sugar cube, please” OR selection strategies in the buchberger algorithm, (), 49-54 · Zbl 0933.68161
[13] Kreuzer, M.; Robbiano, L., Computational commutative algebra 1, (2000), Springer Heidelberg · Zbl 0956.13008
[14] Kreuzer, M.; Robbiano, L., Computational commutative algebra 2, (2005), Springer Heidelberg · Zbl 1090.13021
[15] Traverso, C., Hilbert functions and the buchberger algorithm, J. symbolic comput., 22, 355-376, (1996) · Zbl 0922.13019
[16] Ufnarovski, V., On the cancellation rule in the homogenization, Comput. sci. J. Moldova, 16, 133-145, (2008) · Zbl 1166.13034
[17] Yan, T., The geobucket data structure for polynomials, J. symbolic comput., 25, 285-293, (1998) · Zbl 0927.68124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.