Gröbner bases

Introduction

AlgebraicSolving allows to compute Gröbner bases for input generators over finite fields of characteristic smaller $2^{31}$ w.r.t. the degree reverse lexicographical monomial order.

At the moment different variants of Faugère's F4 Algorithm are implemented as well as a signature based algorithm to compute Gröbner bases.

Functionality

AlgebraicSolving.groebner_basis — Method

groebner_basis(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)

Compute a Groebner basis of the ideal I w.r.t. to the degree reverse lexicographical monomial ordering using Faugère's F4 algorithm. At the moment the underlying algorithm is based on variants of Faugère's F4 Algorithm.

Note: At the moment only ground fields of characteristic p, p prime, p < 2^{31} are supported.

Arguments

I::Ideal{T} where T <: MPolyRingElem: input generators.
initial_hts::Int=17: initial hash table size log_2.
nr_thrds::Int=1: number of threads for parallel linear algebra.
max_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.
la_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).
eliminate::Int=0: size of first block of variables to be eliminated.
complete_reduction::Bool=true: compute a reduced Gröbner basis for I
info_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).

Examples

julia> using AlgebraicSolving

julia> R, (x,y,z) = polynomial_ring(GF(101),["x","y","z"], ordering=:degrevlex)
(Multivariate polynomial ring in 3 variables over GF(101), fpMPolyRingElem[x, y, z])

julia> I = Ideal([x+2*y+2*z-1, x^2+2*y^2+2*z^2-x, 2*x*y+2*y*z-y])
fpMPolyRingElem[x + 2*y + 2*z + 100, x^2 + 2*y^2 + 2*z^2 + 100*x, 2*x*y + 2*y*z + 100*y]

julia> groebner_basis(I)
4-element Vector{fpMPolyRingElem}:
 x + 2*y + 2*z + 100
 y*z + 82*z^2 + 10*y + 40*z
 y^2 + 60*z^2 + 20*y + 81*z
 z^3 + 28*z^2 + 64*y + 13*z

julia> groebner_basis(I, eliminate=2)
1-element Vector{fpMPolyRingElem}:
 z^4 + 38*z^3 + 95*z^2 + 95*z

source

The engine supports the elimination of one block of variables considering the product monomial ordering of two blocks, both ordered w.r.t. the degree reverse lexicographical order. One can either directly add the number of variables of the first block via the eliminate parameter in the groebner_basis call. We have also implemented an alias for this call:

AlgebraicSolving.eliminate — Method

eliminate(I::Ideal{T} where T <: MPolyRingElem, eliminate::Int,  <keyword arguments>)

Compute a Groebner basis of the ideal I w.r.t. to the product monomial ordering defined by two blocks w.r.t. the degree reverse lexicographical monomial ordering using Faugère's F4 algorithm. Hereby the first block includes the first eliminate variables.

At the moment the underlying algorithm is based on variants of Faugère's F4 Algorithm.

Note: At the moment only ground fields of characteristic p, p prime, p < 2^{31} are supported.

Arguments

I::Ideal{T} where T <: MPolyRingElem: input generators.
initial_hts::Int=17: initial hash table size log_2.
nr_thrds::Int=1: number of threads for parallel linear algebra.
max_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.
la_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).
complete_reduction::Bool=true: compute a reduced Gröbner basis for I
info_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).

Examples

julia> using AlgebraicSolving

julia> R, (x,y,z) = polynomial_ring(GF(101),["x","y","z"], ordering=:degrevlex)
(Multivariate polynomial ring in 3 variables over GF(101), fpMPolyRingElem[x, y, z])

julia> I = Ideal([x+2*y+2*z-1, x^2+2*y^2+2*z^2-x, 2*x*y+2*y*z-y])
fpMPolyRingElem[x + 2*y + 2*z + 100, x^2 + 2*y^2 + 2*z^2 + 100*x, 2*x*y + 2*y*z + 100*y]

julia> eliminate(I, 2)
1-element Vector{fpMPolyRingElem}:
 z^4 + 38*z^3 + 95*z^2 + 95*z

source

To compute signature Gröbner bases use

AlgebraicSolving.sig_groebner_basis — Method

sig_groebner_basis(sys::Vector{T}; info_level::Int = 0, degbound::Int = 0) where {T <: MPolyRingElem}

Compute a Signature Gröbner basis of the sequence sys w.r.t. to the degree reverse lexicographical monomial ordering and the degree position-over-term ordering induced by sys. The output is a vector of Tuple{Tuple{Int64, T}, T} where the first element indicates the signature and the second the underlying polynomial.

Note: At the moment only ground fields of characteristic p, p prime, p < 2^{31} are supported. Note: The input generators must be homogeneous. Note: The algorithms behaviour may depend heavily on how the elements in sys are sorted.

Arguments

sys::Vector{T} where T <: MpolyElem: input generators.
info_level::Int=0: info level printout: off (0, default), computational details (1)
degbound::Int=0: degree bound for Gröbner basis computation, compute a full Gröbner basis if 0 (default) or only up to degree d.

Example

julia> using AlgebraicSolving

julia> R, vars = polynomial_ring(GF(17), ["x$i" for i in 1:4])
(Multivariate polynomial ring in 4 variables over GF(17), fpMPolyRingElem[x1, x2, x3, x4])

julia> F = AlgebraicSolving.cyclic(R)
fpMPolyRingElem[x1 + x2 + x3 + x4, x1*x2 + x1*x4 + x2*x3 + x3*x4, x1*x2*x3 + x1*x2*x4 + x1*x3*x4 + x2*x3*x4, x1*x2*x3*x4 + 16]

julia> Fhom = AlgebraicSolving._homogenize(F.gens)
4-element Vector{fpMPolyRingElem}:
 x1 + x2 + x3 + x4
 x1*x2 + x2*x3 + x1*x4 + x3*x4
 x1*x2*x3 + x1*x2*x4 + x1*x3*x4 + x2*x3*x4
 x1*x2*x3*x4 + 16*x5^4

julia> sig_groebner_basis(Fhom)
7-element Vector{Tuple{Tuple{Int64, fpMPolyRingElem}, fpMPolyRingElem}}:
 ((1, 1), x1 + x2 + x3 + x4)
 ((2, 1), x2^2 + 2*x2*x4 + x4^2)
 ((3, 1), x2*x3^2 + x3^2*x4 + 16*x2*x4^2 + 16*x4^3)
 ((4, 1), x2*x3*x4^2 + x3^2*x4^2 + 16*x2*x4^3 + x3*x4^3 + 16*x4^4 + 16*x5^4)
 ((4, x3), x3^3*x4^2 + x3^2*x4^3 + 16*x3*x5^4 + 16*x4*x5^4)
 ((4, x2), x2*x4^4 + x4^5 + 16*x2*x5^4 + 16*x4*x5^4)
 ((4, x2*x3), x3^2*x4^4 + x2*x3*x5^4 + 16*x2*x4*x5^4 + x3*x4*x5^4 + 15*x4^2*x5^4)

source