Educational versions of Groebner basis algorithms¶
Following [BW1993], the original Buchberger algorithm (algorithm GROEBNER in [BW1993]) and an improved version of Buchberger’s algorithm (algorithm GROEBNERNEW2 in [BW1993]) are implemented.
No attempt was made to optimize either algorithm as the emphasis of these
implementations is a clean and easy presentation. To compute a Groebner basis
most efficiently in Sage, use the MPolynomialIdeal.groebner_basis()
method on multivariate polynomial objects instead.
Note
The notion of ‘term’ and ‘monomial’ in [BW1993] is swapped from the notion of those words in Sage (or the other way around, however you prefer it). In Sage a term is a monomial multiplied by a coefficient, while in [BW1993] a monomial is a term multiplied by a coefficient. Also, what is called LM (the leading monomial) in Sage is called HT (the head term) in [BW1993].
EXAMPLES:
Consider Katsura-6 with respect to a degrevlex
ordering.
sage: # needs sage.libs.singular sage.rings.finite_rings
sage: from sage.rings.polynomial.toy_buchberger import *
sage: P.<a,b,c,e,f,g,h,i,j,k> = PolynomialRing(GF(32003))
sage: I = sage.rings.ideal.Katsura(P, 6)
sage: g1 = buchberger(I)
sage: g2 = buchberger_improved(I)
sage: g3 = I.groebner_basis()
>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> from sage.rings.polynomial.toy_buchberger import *
>>> P = PolynomialRing(GF(Integer(32003)), names=('a', 'b', 'c', 'e', 'f', 'g', 'h', 'i', 'j', 'k',)); (a, b, c, e, f, g, h, i, j, k,) = P._first_ngens(10)
>>> I = sage.rings.ideal.Katsura(P, Integer(6))
>>> g1 = buchberger(I)
>>> g2 = buchberger_improved(I)
>>> g3 = I.groebner_basis()
# needs sage.libs.singular sage.rings.finite_rings from sage.rings.polynomial.toy_buchberger import * P.<a,b,c,e,f,g,h,i,j,k> = PolynomialRing(GF(32003)) I = sage.rings.ideal.Katsura(P, 6) g1 = buchberger(I) g2 = buchberger_improved(I) g3 = I.groebner_basis()
All algorithms actually compute a Groebner basis:
sage: # needs sage.libs.singular sage.rings.finite_rings
sage: Ideal(g1).basis_is_groebner()
True
sage: Ideal(g2).basis_is_groebner()
True
sage: Ideal(g3).basis_is_groebner()
True
>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> Ideal(g1).basis_is_groebner()
True
>>> Ideal(g2).basis_is_groebner()
True
>>> Ideal(g3).basis_is_groebner()
True
# needs sage.libs.singular sage.rings.finite_rings Ideal(g1).basis_is_groebner() Ideal(g2).basis_is_groebner() Ideal(g3).basis_is_groebner()
The results are correct:
sage: # needs sage.libs.singular sage.rings.finite_rings
sage: Ideal(g1) == Ideal(g2) == Ideal(g3)
True
>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> Ideal(g1) == Ideal(g2) == Ideal(g3)
True
# needs sage.libs.singular sage.rings.finite_rings Ideal(g1) == Ideal(g2) == Ideal(g3)
If get_verbose()
is \(\ge 1\), a protocol is provided:
sage: # needs sage.libs.singular sage.rings.finite_rings
sage: from sage.misc.verbose import set_verbose
sage: set_verbose(1)
sage: P.<a,b,c> = PolynomialRing(GF(127))
sage: I = sage.rings.ideal.Katsura(P)
// sage... ideal
sage: I
Ideal (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b)
of Multivariate Polynomial Ring in a, b, c over Finite Field of size 127
sage: buchberger(I) # random
(a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => -2*b^2 - 6*b*c - 6*c^2 + b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
(a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
(a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
(2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
(2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => -22*c^3 + 24*c^2 - 60*b - 62*c
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(2*a*b + 2*b*c - b, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(a + 2*b + 2*c - 1, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(-5*b*c - 6*c^2 - 63*b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(2*a*b + 2*b*c - b, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
(a^2 + 2*b^2 + 2*c^2 - a, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
15 reductions to zero.
[a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]
>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> from sage.misc.verbose import set_verbose
>>> set_verbose(Integer(1))
>>> P = PolynomialRing(GF(Integer(127)), names=('a', 'b', 'c',)); (a, b, c,) = P._first_ngens(3)
>>> I = sage.rings.ideal.Katsura(P)
// sage... ideal
>>> I
Ideal (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b)
of Multivariate Polynomial Ring in a, b, c over Finite Field of size 127
>>> buchberger(I) # random
(a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => -2*b^2 - 6*b*c - 6*c^2 + b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => -22*c^3 + 24*c^2 - 60*b - 62*c
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(-5*b*c - 6*c^2 - 63*b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
15 reductions to zero.
[a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]
# needs sage.libs.singular sage.rings.finite_rings from sage.misc.verbose import set_verbose set_verbose(1) P.<a,b,c> = PolynomialRing(GF(127)) I = sage.rings.ideal.Katsura(P) I buchberger(I) # random
The original Buchberger algorithm performs 15 useless reductions to zero for this example:
sage: # needs sage.libs.singular sage.rings.finite_rings
sage: gb = buchberger(I)
...
15 reductions to zero.
>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> gb = buchberger(I)
...
15 reductions to zero.
# needs sage.libs.singular sage.rings.finite_rings gb = buchberger(I)
The ‘improved’ Buchberger algorithm in contrast only performs 1 reduction to zero:
sage: # needs sage.libs.singular sage.rings.finite_rings
sage: gb = buchberger_improved(I)
...
1 reductions to zero.
sage: sorted(gb)
[a + 2*b + 2*c - 1, b*c + 52*c^2 + 38*b + 25*c,
b^2 - 26*c^2 - 51*b + 51*c, c^3 + 22*c^2 - 55*b + 49*c]
>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> gb = buchberger_improved(I)
...
1 reductions to zero.
>>> sorted(gb)
[a + 2*b + 2*c - 1, b*c + 52*c^2 + 38*b + 25*c,
b^2 - 26*c^2 - 51*b + 51*c, c^3 + 22*c^2 - 55*b + 49*c]
# needs sage.libs.singular sage.rings.finite_rings gb = buchberger_improved(I) sorted(gb)
AUTHORS:
Martin Albrecht (2007-05-24): initial version
Marshall Hampton (2009-07-08): some doctest additions
- sage.rings.polynomial.toy_buchberger.buchberger(F)[source]¶
Compute a Groebner basis using the original version of Buchberger’s algorithm as presented in [BW1993], page 214.
INPUT:
F
– an ideal in a multivariate polynomial ring
OUTPUT: a Groebner basis for F
Note
The verbosity of this function may be controlled with a
set_verbose()
call. Any value >=1 will result in this function printing intermediate bases.EXAMPLES:
sage: from sage.rings.polynomial.toy_buchberger import buchberger sage: R.<x,y,z> = PolynomialRing(QQ) sage: I = R.ideal([x^2 - z - 1, z^2 - y - 1, x*y^2 - x - 1]) sage: set_verbose(0) sage: gb = buchberger(I) # needs sage.libs.singular sage: gb.is_groebner() # needs sage.libs.singular True sage: gb.ideal() == I # needs sage.libs.singular True
>>> from sage.all import * >>> from sage.rings.polynomial.toy_buchberger import buchberger >>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3) >>> I = R.ideal([x**Integer(2) - z - Integer(1), z**Integer(2) - y - Integer(1), x*y**Integer(2) - x - Integer(1)]) >>> set_verbose(Integer(0)) >>> gb = buchberger(I) # needs sage.libs.singular >>> gb.is_groebner() # needs sage.libs.singular True >>> gb.ideal() == I # needs sage.libs.singular True
from sage.rings.polynomial.toy_buchberger import buchberger R.<x,y,z> = PolynomialRing(QQ) I = R.ideal([x^2 - z - 1, z^2 - y - 1, x*y^2 - x - 1]) set_verbose(0) gb = buchberger(I) # needs sage.libs.singular gb.is_groebner() # needs sage.libs.singular gb.ideal() == I # needs sage.libs.singular
- sage.rings.polynomial.toy_buchberger.buchberger_improved(F)[source]¶
Compute a Groebner basis using an improved version of Buchberger’s algorithm as presented in [BW1993], page 232.
This variant uses the Gebauer-Moeller Installation to apply Buchberger’s first and second criterion to avoid useless pairs.
INPUT:
F
– an ideal in a multivariate polynomial ring
OUTPUT: a Groebner basis for F
Note
The verbosity of this function may be controlled with a
set_verbose()
call. Any value>=1
will result in this function printing intermediate Groebner bases.EXAMPLES:
sage: from sage.rings.polynomial.toy_buchberger import buchberger_improved sage: R.<x,y,z> = PolynomialRing(QQ) sage: set_verbose(0) sage: sorted(buchberger_improved(R.ideal([x^4 - y - z, x*y*z - 1]))) # needs sage.libs.singular [x*y*z - 1, x^3 - y^2*z - y*z^2, y^3*z^2 + y^2*z^3 - x^2]
>>> from sage.all import * >>> from sage.rings.polynomial.toy_buchberger import buchberger_improved >>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3) >>> set_verbose(Integer(0)) >>> sorted(buchberger_improved(R.ideal([x**Integer(4) - y - z, x*y*z - Integer(1)]))) # needs sage.libs.singular [x*y*z - 1, x^3 - y^2*z - y*z^2, y^3*z^2 + y^2*z^3 - x^2]
from sage.rings.polynomial.toy_buchberger import buchberger_improved R.<x,y,z> = PolynomialRing(QQ) set_verbose(0) sorted(buchberger_improved(R.ideal([x^4 - y - z, x*y*z - 1]))) # needs sage.libs.singular
- sage.rings.polynomial.toy_buchberger.inter_reduction(Q)[source]¶
Compute inter-reduced polynomials from a set of polynomials.
INPUT:
Q
– set of polynomials
OUTPUT:
if
Q
is the set \(f_1, ..., f_n\), this method returns \(g_1, ..., g_s\) such that:\((f_1,...,f_n) = (g_1,...,g_s)\)
\(LM(g_i) \neq LM(g_j)\) for all \(i \neq j\)
\(LM(g_i)\) does not divide \(m\) for all monomials \(m\) of \(\{g_1,...,g_{i-1}, g_{i+1},...,g_s\}\)
\(LC(g_i) = 1\) for all \(i\).
EXAMPLES:
sage: from sage.rings.polynomial.toy_buchberger import inter_reduction sage: inter_reduction(set()) set()
>>> from sage.all import * >>> from sage.rings.polynomial.toy_buchberger import inter_reduction >>> inter_reduction(set()) set()
from sage.rings.polynomial.toy_buchberger import inter_reduction inter_reduction(set())
sage: P.<x,y> = QQ[] sage: reduced = inter_reduction(set([x^2 - 5*y^2, x^3])) # needs sage.libs.singular sage: reduced == set([x*y^2, x^2 - 5*y^2]) # needs sage.libs.singular True sage: reduced == inter_reduction(set([2*(x^2 - 5*y^2), x^3])) # needs sage.libs.singular True
>>> from sage.all import * >>> P = QQ['x, y']; (x, y,) = P._first_ngens(2) >>> reduced = inter_reduction(set([x**Integer(2) - Integer(5)*y**Integer(2), x**Integer(3)])) # needs sage.libs.singular >>> reduced == set([x*y**Integer(2), x**Integer(2) - Integer(5)*y**Integer(2)]) # needs sage.libs.singular True >>> reduced == inter_reduction(set([Integer(2)*(x**Integer(2) - Integer(5)*y**Integer(2)), x**Integer(3)])) # needs sage.libs.singular True
P.<x,y> = QQ[] reduced = inter_reduction(set([x^2 - 5*y^2, x^3])) # needs sage.libs.singular reduced == set([x*y^2, x^2 - 5*y^2]) # needs sage.libs.singular reduced == inter_reduction(set([2*(x^2 - 5*y^2), x^3])) # needs sage.libs.singular
>>> from sage.all import * >>> P = QQ['x, y']; (x, y,) = P._first_ngens(2) >>> reduced = inter_reduction(set([x**Integer(2) - Integer(5)*y**Integer(2), x**Integer(3)])) # needs sage.libs.singular >>> reduced == set([x*y**Integer(2), x**Integer(2) - Integer(5)*y**Integer(2)]) # needs sage.libs.singular True >>> reduced == inter_reduction(set([Integer(2)*(x**Integer(2) - Integer(5)*y**Integer(2)), x**Integer(3)])) # needs sage.libs.singular True
P.<x,y> = QQ[] reduced = inter_reduction(set([x^2 - 5*y^2, x^3])) # needs sage.libs.singular reduced == set([x*y^2, x^2 - 5*y^2]) # needs sage.libs.singular reduced == inter_reduction(set([2*(x^2 - 5*y^2), x^3])) # needs sage.libs.singular
- sage.rings.polynomial.toy_buchberger.select(P)[source]¶
Select a polynomial using the normal selection strategy.
INPUT:
P
– list of critical pairs
OUTPUT: an element of P
EXAMPLES:
sage: from sage.rings.polynomial.toy_buchberger import select sage: R.<x,y,z> = PolynomialRing(QQ, order='lex') sage: ps = [x^3 - z - 1, z^3 - y - 1, x^5 - y - 2] sage: pairs = [[ps[i], ps[j]] for i in range(3) for j in range(i + 1, 3)] sage: select(pairs) [x^3 - z - 1, -y + z^3 - 1]
>>> from sage.all import * >>> from sage.rings.polynomial.toy_buchberger import select >>> R = PolynomialRing(QQ, order='lex', names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3) >>> ps = [x**Integer(3) - z - Integer(1), z**Integer(3) - y - Integer(1), x**Integer(5) - y - Integer(2)] >>> pairs = [[ps[i], ps[j]] for i in range(Integer(3)) for j in range(i + Integer(1), Integer(3))] >>> select(pairs) [x^3 - z - 1, -y + z^3 - 1]
from sage.rings.polynomial.toy_buchberger import select R.<x,y,z> = PolynomialRing(QQ, order='lex') ps = [x^3 - z - 1, z^3 - y - 1, x^5 - y - 2] pairs = [[ps[i], ps[j]] for i in range(3) for j in range(i + 1, 3)] select(pairs)
- sage.rings.polynomial.toy_buchberger.spol(f, g)[source]¶
Compute the S-polynomial of f and g.
INPUT:
f
,g
– polynomials
OUTPUT: the S-polynomial of f and g
EXAMPLES:
sage: R.<x,y,z> = PolynomialRing(QQ) sage: from sage.rings.polynomial.toy_buchberger import spol sage: spol(x^2 - z - 1, z^2 - y - 1) x^2*y - z^3 + x^2 - z^2
>>> from sage.all import * >>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3) >>> from sage.rings.polynomial.toy_buchberger import spol >>> spol(x**Integer(2) - z - Integer(1), z**Integer(2) - y - Integer(1)) x^2*y - z^3 + x^2 - z^2
R.<x,y,z> = PolynomialRing(QQ) from sage.rings.polynomial.toy_buchberger import spol spol(x^2 - z - 1, z^2 - y - 1)
- sage.rings.polynomial.toy_buchberger.update(G, B, h)[source]¶
Update
G
using the set of critical pairsB
and the polynomialh
as presented in [BW1993], page 230. For this, Buchberger’s first and second criterion are tested.This function implements the Gebauer-Moeller Installation.
INPUT:
G
– an intermediate Groebner basisB
– set of critical pairsh
– a polynomial
OUTPUT: a tuple of
an intermediate Groebner basis
a set of critical pairs
EXAMPLES:
sage: from sage.rings.polynomial.toy_buchberger import update sage: R.<x,y,z> = PolynomialRing(QQ) sage: set_verbose(0) sage: update(set(), set(), x*y*z) ({x*y*z}, set()) sage: G, B = update(set(), set(), x*y*z - 1) sage: G, B = update(G, B, x*y^2 - 1) sage: G, B ({x*y*z - 1, x*y^2 - 1}, {(x*y^2 - 1, x*y*z - 1)})
>>> from sage.all import * >>> from sage.rings.polynomial.toy_buchberger import update >>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3) >>> set_verbose(Integer(0)) >>> update(set(), set(), x*y*z) ({x*y*z}, set()) >>> G, B = update(set(), set(), x*y*z - Integer(1)) >>> G, B = update(G, B, x*y**Integer(2) - Integer(1)) >>> G, B ({x*y*z - 1, x*y^2 - 1}, {(x*y^2 - 1, x*y*z - 1)})
from sage.rings.polynomial.toy_buchberger import update R.<x,y,z> = PolynomialRing(QQ) set_verbose(0) update(set(), set(), x*y*z) G, B = update(set(), set(), x*y*z - 1) G, B = update(G, B, x*y^2 - 1) G, B