Usage

The Gröbner walk is an approach to reduce the computational complexity of Gröbner basis computations as proposed by [AGK97]. These incarnations of the Gröbner walk refer to a family of algorithms that perform a reverse local search on the cones of the Gröbner fan. Then, a Gröbner basis is calculated for each encountered cone while reusing the generators obtained from the previous cone.

The implemented algorithms may be accessed using the following function.

groebner_walkFunction
groebner_walk(
  I::MPolyIdeal, 
  target::MonomialOrdering = lex(base_ring(I)),
  start::MonomialOrdering = default_ordering(base_ring(I));
  perturbation_degree = ngens(base_ring(I)),
  algorithm::Symbol = :standard
)

Compute a reduced Groebner basis w.r.t. to the monomial ordering target by converting it from a Groebner basis with respect to the ordering start using the Groebner Walk.

Arguments

  • I::MPolyIdeal: ideal one wants to compute a Groebner basis for.
  • target::MonomialOrdering=:lex: monomial ordering one wants to compute a Groebner basis for.
  • start::MonomialOrdering=:degrevlex: monomial ordering to begin the conversion.
  • perturbationDegree::Int=2: the perturbation degree for the perturbed Walk.
  • algorithm::Symbol=:standard: strategy of the Groebner Walk. One can choose between:
    • standard: Standard Walk [CLO05],
    • generic: Generic Walk [FJLT07],
    • perturbed: Perturbed Walk [AGK96].

Examples

julia> R,(x,y) = polynomial_ring(QQ, [:x,:y]);

julia> I = ideal([y^4+ x^3-x^2+x,x^4]);

julia> groebner_walk(I, lex(R))
Gröbner basis with elements
  1 -> x + y^12 - y^8 + y^4
  2 -> y^16
with respect to the ordering
  lex([x, y])

julia> groebner_walk(I, lex(R); algorithm=:generic)
Gröbner basis with elements
  1 -> y^16
  2 -> x + y^12 - y^8 + y^4
with respect to the ordering
  lex([x, y])

julia> set_verbosity_level(:groebner_walk, 1);

julia> groebner_walk(I, lex(R))
Results for standard_walk
Crossed Cones in: 
ZZRingElem[1, 1]
ZZRingElem[4, 3]
ZZRingElem[4, 1]
ZZRingElem[12, 1]
Cones crossed: 4
Gröbner basis with elements
  1 -> x + y^12 - y^8 + y^4
  2 -> y^16
with respect to the ordering
  lex([x, y])
Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source