Usage

The Gröbner walk is an approach to reduce the computational complexity of Gröbner basis computations that was originally proposed in [AGK97].

This is done by performing 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_walk — Function

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

Compute a reduced Groebner basis w.r.t. to a monomial ordering by converting it 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.
algorithm::Symbol=:standard: strategy of the Groebner Walk. One can choose between:
- standard: Standard Walk [CLO05],
- generic: Generic Walk [FJLT07].

Examples

julia> using Oscar
  ___   ___   ___    _    ____
 / _ \ / __\ / __\  / \  |  _ \  | Combining and extending ANTIC, GAP,
| |_| |\__ \| |__  / ^ \ |  ´ /  | Polymake and Singular
 \___/ \___/ \___//_/ \_\|_|\_\  | Type "?Oscar" for more information
o--------o-----o-----o--------o  | Documentation: https://docs.oscar-system.org
  S Y M B O L I C   T O O L S    | Version 1.4.1

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])

source