×

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
PDFBibTeX XMLCite
Full Text: DOI arXiv

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.; 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.; 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, (Proc. EUROSAM 79. Proc. EUROSAM 79, Springer LNCS, vol. 72 (1979)), 3-21 · Zbl 0417.68029
[5] Buchberger, B., Groebner bases: an algorithmic method in polynomial ideal theory, (Bose, N. K., Multidimensional Systems Theory (1985), D. Reidel Publ. Comp.), 184-232 · Zbl 0587.13009
[6] Caboara, M., De Dominicis, G., Robbiano, L., 1996. Multigraded Hilbert functions and Buchberger algorithm. In: Proc. of the ISSAC’96. pp. 72-85.; 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; 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), (Mora, T., Proceedings of ISSAC 2002 (2002), ACM Press), 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, (Watt, S. M., Proceedings of ISSAC. Proceedings of ISSAC, Bonn 1991 (1991), ACM Press), 49-54 · Zbl 0933.68161
[13] Kreuzer, M.; Robbiano, L., Computational Commutative Algebra 1 (2000), Springer: Springer Heidelberg · Zbl 0956.13008
[14] Kreuzer, M.; Robbiano, L., Computational Commutative Algebra 2 (2005), Springer: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.