×

zbMATH — the first resource for mathematics

Slimgb: Gröbner bases with slim polynomials. (English) Zbl 1200.13044
A modification of Buchberger’s algorithm to compute Gröbner bases is presented in order to avoid intermediate coefficient swell. The aim is to keep polynomials short and coefficients small during the computation. One of the basic ideas is the concept of a weighted length of a polynomial (a suitable combination of the number of terms of the polynomial, its ecart and the coefficient size). Polynomials of shortest length are used in the reduction process, members of the actual Gröbner basis will be exchanged by shorter intermediate results if possible. This modification of Buchberger’s algorithm, called slimbg, is implemented in the computer algebra system Singular. Experiments show (timings are given in the paper) that the algorithm for many examples is much more efficient than the “ordinary” Gröbner basis algorithm.

MSC:
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bachmann, O., Schönemann, H.: Monomial operations for computations of Gröbner bases. In: Reports On Computer Algebra 18. Centre for Computer Algebra, University of Kaiserslautern (January 1998). Also available from http://www.mathematik.uni-kl.de/\(\sim\)zca/ · Zbl 0924.68104
[2] Becker, T., Weispfennig, V.: Gröbner Bases, a Computational Approach to Commutative Algebra. Graduate Texts in Mathematics. Springer, Berlin (1993)
[3] Brickenstein, M.: Neue Varianten zur Berechnung von Gröbnerbasen. Diplomarbeit, Universität Kaiserslautern (2004)
[4] Brickenstein, M., Dreyer, A.: Polybori: A framework for Gröbner-basis computations with Boolean polynomials. J. Symb. Comput. 44(9), 1326–1345 (2009). Effective Methods in Algebraic Geometry · Zbl 1186.68571 · doi:10.1016/j.jsc.2008.02.017
[5] Brickenstein, M., Bulygin, S., King, S., Levandovskyy, V., Diaz Toca, G.M.: Examples for slimgb (2006)
[6] Buchberger, B.: A criterion for detecting unnecessary reductions in the construction of a Gröbner basis. In: Bose, N.K. (ed.) Recent Trends in Multidimensional System Theory (1985) · Zbl 0417.68029
[7] Caboara, M., Kreuzer, M., Robbiano, L.: Efficiently computing minimal sets of critical pairs. J. Symb. Comput. 38, 1169–1190 (2004) · Zbl 1137.13315 · doi:10.1016/j.jsc.2003.08.009
[8] Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F 4). J. Pure Appl. Algebra 139(1–3), 61–88 (1999) · Zbl 0930.68174 · doi:10.1016/S0022-4049(99)00005-5
[9] Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5). In: Proc. of the International Symposium on Symbolic and Algebraic Computation (ISSAC’02), pp. 75–83. ACM Press, New York (2002) · Zbl 1072.68664
[10] Giovini, A., Mora, T., Niesi, G., Robbiano, L., Traverso, C.: One sugar cube, please or selection strategies in Buchberger algorithms. In: Watt, S. (ed.) Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computations, ISSAC’91, pp. 49–54. ACM Press, New York (1991) · Zbl 0933.68161
[11] Greuel, G.-M., Pfister, G.: A SINGULAR Introduction to Commutative Algebra. Springer, Berlin (2002) · Zbl 1023.13001
[12] Greuel, G.-M., Pfister, G., Schönemann, H.: Singular 3.0. A computer algebra system for polynomial computations. Centre for Computer Algebra, University of Kaiserslautern (2005). http://www.singular.uni-kl.de · Zbl 1344.13002
[13] Levandovskyy, V.: Non-commutative computer algebra for polynomial algebras: Gröbner bases, applications and implementation. Doctoral Thesis, Universität Kaiserslautern (2005). Available from http://kluedo.ub.uni-kl.de/volltexte/2005/1883/
[14] The Symbolic Data Project, 2000–2006. http://www.SymbolicData.org · Zbl 1189.65154
[15] Yan, T.: The geobucket data structure for polynomials. J. Symb. Comput. 25(3), 285–294 (1998) · Zbl 0927.68124 · doi:10.1006/jsco.1997.0176
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.