Up One Level SAGE Reference Manual Contents Module Index Index
Previous: Up: 33. Combinatorial Geometry Next:

33.2 Groebner Fans

Module: sage.rings.polynomial.groebner_fan

Groebner Fans

SAGE provides much of the functionality of gfan, which is a software package whose main function is to enumerate all reduced Gröbner bases of a polynomial ideal. The reduced Gröbner bases yield the maximal cones in the Gröbner fan of the ideal. Several subcomputations can be issued and additional tools are included. Among these the highlights are:

- Anders Nedergaard Jensen: Wrote the gfan C++ program, which implements algorithms many of which were invented by Jensen, Komei Fukuda, and Rekha Thomas. All the underlying hard work of the Groebner fans functionality of SAGE depends on this C++ program.

- William Stein (2006-04-20): Wrote first version of the SAGE code for working with Groebner fans.

- Tristram Bogart (bogart@math): the design of the SAGE interface to gfan is joint work with Tristram Bogart, who also supplied numerous examples. 

sage: x,y = QQ['x,y'].gens() 
sage: i = ideal(x^2 - y^2 + 1)
sage: g = i.groebner_fan()
sage: g.reduced_groebner_bases()
[[x^2 - y^2 + 1], [-x^2 + y^2 - 1]]

TESTS: 

sage: x,y = QQ['x,y'].gens() 
sage: i = ideal(x^2 - y^2 + 1)
sage: g = i.groebner_fan()
sage: g == loads(dumps(g))
True

Class: GroebnerFan

class GroebnerFan
GroebnerFan( self, I, [is_groebner_basis=False], [symmetry=None], [verbose=False])
INPUT:
            I -- ideal in a multivariate polynomial ring
            is_groebner_basis -- bool (default False).  if True, then
                         I.gens() must be a Groebner basis with
                         respect to the standard degree lexicographic
                         term order.
            symmetry -- default: None; if not None, describes symmetries
                        of the ideal
            verbose  -- default: False; if True, printout useful info
                        during computations


sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
sage: I = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y])
sage: G = I.groebner_fan(); G
Groebner fan of the ideal:
Ideal (x^2*y - z, -x + y^2*z, x*z^2 - y) of Multivariate Polynomial Ring in
x, y, z over Rational Field

Functions: buchberger,$ $ characteristic,$ $ dimension_of_homogeneity_space,$ $ fvector,$ $ gfan,$ $ homogeneity_space,$ $ ideal,$ $ interactive,$ $ maximal_total_degree_of_a_groebner_basis,$ $ minimal_total_degree_of_a_groebner_basis,$ $ number_of_reduced_groebner_bases,$ $ number_of_variables,$ $ reduced_groebner_bases,$ $ render,$ $ ring,$ $ tropical_basis,$ $ universal_groebner_basis

buchberger( self)
Computes and returns a lexicographic reduced Groebner basis for the ideal. 

sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: G = R.ideal([x - z^3, y^2 - x + x^2 - z^3*x]).groebner_fan()
sage: G.buchberger ()
[-z^3 + y^2, -z^3 + x]

characteristic( self)
Return the characteristic of the base ring.

dimension_of_homogeneity_space( self)
Return the dimension of the homogeneity space. 

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.dimension_of_homogeneity_space()
0

fvector( self)
Return the f-vector for the Grobner fan. 

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.fvector ()
(1, 4, 3)

homogeneity_space( self)
Return the homogeneity space of a the list of polynomials that define this Groebner fan. 

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: H = G.homogeneity_space()

ideal( self)
Return the ideal the was used to define this Groebner fan.

interactive( self)
See the documentation for self[0].interative()

maximal_total_degree_of_a_groebner_basis( self)
Return the maximal total degree of any Groebner basis. 

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.maximal_total_degree_of_a_groebner_basis()
4

minimal_total_degree_of_a_groebner_basis( self)
Return the minimal total degree of any Groebner basis. 

sage: R.<x,y> = PolynomialRing(QQ,2)        
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.minimal_total_degree_of_a_groebner_basis()
2

number_of_reduced_groebner_bases( self)
Return the number of reduced Groebner bases. 

sage: R.<x,y> = PolynomialRing(QQ,2)                
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.number_of_reduced_groebner_bases()
3

number_of_variables( self)
Return the number of variables. 

sage: R.<x,y> = PolynomialRing(QQ,2)                         
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.number_of_variables()
2


sage: R = PolynomialRing(QQ,'x',10)
sage: R.inject_variables(globals())
Defining x0, x1, x2, x3, x4, x5, x6, x7, x8, x9
sage: G = ideal([x0 - x9, sum(R.gens())]).groebner_fan()
sage: G.number_of_variables()
10

reduced_groebner_bases( self)

sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
sage: G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: X = G.reduced_groebner_bases()
sage: len(X)
33
sage: X[0]
[z^15 - z, y - z^11, x - z^9]
sage: X[0].ideal()
Ideal (z^15 - z, y - z^11, x - z^9) of Multivariate Polynomial Ring in x,
y, z over Rational Field
sage: X[:5]
[[z^15 - z, y - z^11, x - z^9],
[-y + z^11, y*z^4 - z, y^2 - z^8, x - z^9],
[-y^2 + z^8, y*z^4 - z, y^2*z^3 - y, y^3 - z^5, x - y^2*z],
[-y^3 + z^5, y*z^4 - z, y^2*z^3 - y, y^4 - z^2, x - y^2*z],
[-y^4 + z^2, y^6*z - y, y^9 - z, x - y^2*z]]

render( self, file, [larger=False], [shift=0], [show=False])
Render a Groebner fan as an xfig file.

More precisely, the output is a drawing of the Groebner fan intersected with a traingle. The corners of the triangle are (1,0,0) to the right, (0,1,0) to the left and (0,0,1) at the top. If there are more than three variables in the ring we extend these coordinates with zeros. 

INPUT:
    shift -- shift the positions of the variables in
             the drawing.  For example, with shift=1,
             the corners will be b (right), c (left),
             and d (top).  The shifting is done modulo
             the number of variables in the polynomial
             ring.   The default is 0.
    larger -- bool (default: False); if True, make
             the triangle larger so that the shape of
             of the Groebner region appears.
    show  -- bool (default: True); if True, pop up
             xfig displaying the resulting file (this
             requires xfig).


sage: R.<x,y> = PolynomialRing(QQ,2)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.render(SAGE_TMP + '/test.fig')


sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G.render(SAGE_TMP + '/test.fig', show=False, larger=True)

ring( self)
Return the multivariate polynomial ring.

tropical_basis( self, [check=True])
Return a tropical basis for the tropical curve associated to this ideal. 

INPUT:
    check -- bool (default: True); if True raises a ValueError
             exception if this ideal does not define a tropical curve
             (i.e., the condition that R/I has dimension equal
             to 1 + the dimension of the homogeneity space is
             not satisfied).


sage: R.<x,y,z> = PolynomialRing(QQ,3, order='lex')
sage: G = R.ideal([y^3-3*x^2, z^3-x-y-2*y^3+2*x^2]).groebner_fan()
sage: G
Groebner fan of the ideal:
Ideal (-3*x^2 + y^3, 2*x^2 - x - 2*y^3 - y + z^3) of Multivariate
Polynomial Ring in x, y, z over Rational Field
sage: G.tropical_basis ()
[-4*x^2 - x - y + z^3, -3*x^2 + y^3]

Special Functions: __eq__,$ $ __getitem__,$ $ __iter__,$ $ _gfan_ideal,$ $ _gfan_maps,$ $ _gfan_mod,$ $ _gfan_reduced_groebner_bases,$ $ _gfan_stats,$ $ _gfan_vardict,$ $ _repr_

_gfan_ideal( self)
Return the ideal in gfan's notation (with variables mapped to a,b,c, etc.) 

sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G._gfan_ideal()
'{a^2*b - c, b^2*c - a, a*c^2 - b}'

_gfan_maps( self)
INPUT:
            none
        OUTPUT:
            -- map from SAGE ring to gfan ring
            -- map from gfan ring to SAGE ring


sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G._gfan_maps()
(Ring morphism:
  From: Multivariate Polynomial Ring in x, y, z over Rational Field
  To:   Multivariate Polynomial Ring in a, b, c over Rational Field
  Defn: x |--> a
        y |--> b
        z |--> c,
 Ring morphism:
  From: Multivariate Polynomial Ring in a, b, c over Rational Field
  To:   Multivariate Polynomial Ring in x, y, z over Rational Field
  Defn: a |--> x
        b |--> y
        c |--> z)

_gfan_mod( self)
Return the extra options to the gfan command that are used by this object to account for working modulo a prime or in the presence of extra symmetries.

_gfan_stats( self)
Return various statistics about this Groebner fan. 

sage: R.<x,y> = PolynomialRing(QQ)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G._gfan_stats()
{'Number of reduced Groebner bases': 3, 'Maximal total degree of a Groebner
basis': 4, 'Dimension of homogeneity space': 0, 'Number of variables': 2,
'Minimal total degree of a Groebner basis': 2}

Class: ReducedGroebnerBasis

class ReducedGroebnerBasis
ReducedGroebnerBasis( self, groebner_fan, gens, gfan_gens)

Functions: groebner_cone,$ $ ideal,$ $ interactive,$ $ weight_vector

groebner_cone( self, [restrict=False])
Return defining inequalities for the full-dimensional Groebner cone associated to this marked minimal reduced Groebner basis. 

INPUT:
    restrict -- bool (default: False); if True, add an inequality for
                each coordinate, so that the cone is restricted to
                the positive orthant.

OUTPUT:
    tuple of integer vectors


sage: R.<x,y> = PolynomialRing(QQ,2)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G[1].groebner_cone()
((-1, 2), (1, -1))
sage: [g.groebner_cone() for g in G]
[((0, 1), (1, -2)), ((-1, 2), (1, -1)), ((-1, 2), (-1, 1), (1, 0))]
sage: G[1].groebner_cone(restrict=True)
((-1, 2), (1, -1), (1, 0), (0, 1))

ideal( self)
Return the ideal generated by this basis. 

sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: G = R.ideal([x - z^3, y^2 - 13*x]).groebner_fan()
sage: G[0].ideal()
Ideal (-13*z^3 + y^2, -z^3 + x) of Multivariate Polynomial Ring in x, y, z
over Rational Field

interactive( self, [latex=False], [flippable=False], [wall=False], [inequalities=False], [weight=False])
Do an interactive walk of the Groebner fan starting at this reduced Groebner basis. 

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G[0].interactive()      # not tested
Initializing gfan interactive mode
*********************************************
*     Press control-C to return to SAGE     *
*********************************************
....

weight_vector( self)
Return the weight vector of this reduced Groebner basis. 

sage: R.<x,y,z> = PolynomialRing(QQ,3)        
sage: G = R.ideal([x - z^3, y^2 - 3*x]).groebner_fan()
sage: [g.weight_vector() for g in G]
[(4, 2, 1), (3, 1, 1), (4, 3, 2)]


sage: R.<x,y,z> = PolynomialRing(GF(3),3)
sage: G = R.ideal([x - z^3, y^2 - 3*x]).groebner_fan()
sage: [g.weight_vector() for g in G]
[(4, 1, 1), (2, 1, 1)]

Special Functions: _gfan,$ $ _gfan_gens,$ $ _repr_

Up One Level SAGE Reference Manual Contents Module Index Index
Previous: Up: 33. Combinatorial Geometry Next:
Release 2007.10.28, documentation updated on October 28, 2007.
See About this document... for information on suggesting changes.