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_walk
— Functiongroebner_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:
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])
This function is part of the experimental code in Oscar. Please read here for more details.