Slimgb: Gröbner bases with slim polynomials
Tóm tắt
This paper introduces a variation of Buchbergers’s algorithm for computing Gröbner bases in order to avoid intermediate coefficient swell. It is designed to keep coefficients small and polynomials short during the computation. This pays off in computation time as well as memory usage. One of the newly introduced concepts is a weighted length of a polynomial, being a combination of the number of terms, the ecart and the coefficient size and may depend on the ground field and the monomial ordering. Further key features of the algorithm are parallel reductions, exchanging members of the generating system for shorter intermediate results and an extended version of the product criterion. The algorithm is very flexible, the strategy is controlled by a single function which calculates the weighted length of a polynomial. All components of the algorithm depend on this function, hence one can easily customize the whole algorithm to fit the needs of specific problems by adjusting the weighted length. The algorithm—called “slimgb”—is easy to implement in a standard Gröbner basis environment, as usual polynomial data structures are used.
Tài liệu tham khảo
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/~zca/
Becker, T., Weispfennig, V.: Gröbner Bases, a Computational Approach to Commutative Algebra. Graduate Texts in Mathematics. Springer, Berlin (1993)
Brickenstein, M.: Neue Varianten zur Berechnung von Gröbnerbasen. Diplomarbeit, Universität Kaiserslautern (2004)
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
Brickenstein, M., Bulygin, S., King, S., Levandovskyy, V., Diaz Toca, G.M.: Examples for slimgb (2006)
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)
Caboara, M., Kreuzer, M., Robbiano, L.: Efficiently computing minimal sets of critical pairs. J. Symb. Comput. 38, 1169–1190 (2004)
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)
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)
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)
Greuel, G.-M., Pfister, G.: A SINGULAR Introduction to Commutative Algebra. Springer, Berlin (2002)
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
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/
The Symbolic Data Project, 2000–2006. http://www.SymbolicData.org
Yan, T.: The geobucket data structure for polynomials. J. Symb. Comput. 25(3), 285–294 (1998)