Gröbner bases

Introduction

AlgebraicSolving allows to compute Gröbner bases for input generators over prime fields of characteristic smaller $2^{31}$ or over the rationals 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} and the rationals 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.
intersect::Bool=true: compute the eliminate-th elimination ideal.
complete_reduction::Bool=true: compute a reduced Gröbner basis for I.
normalize::Bool=false: normalize generators of Gröbner basis for I, only applicable when working over the rationals.
truncate_lifting::Int=0: truncates the lifting process to given number of elements, only applicable when working over the rationals.
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"], internal_ordering=:degrevlex)
(Multivariate polynomial ring in 3 variables over GF(101), FqMPolyRingElem[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])
FqMPolyRingElem[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{FqMPolyRingElem}:
 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{FqMPolyRingElem}:
 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. By using intersect=false it is possible to only use block ordering without intersecting. 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} and the rationals are supported.

Arguments

I::Ideal{T} where T <: MPolyRingElem: input generators.
eliminate::Int=0: size of first block of variables to be eliminated.
intersect::Bool=true: compute the eliminate-th elimination ideal.
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.
normalize::Bool=false: normalize generators of Gröbner basis for I, only applicable when working over the rationals.
truncate_lifting::Int=0: truncates the lifting process to given number of elements, only applicable when working over the rationals.
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"], internal_ordering=:degrevlex)
(Multivariate polynomial ring in 3 variables over GF(101), FqMPolyRingElem[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])
FqMPolyRingElem[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{FqMPolyRingElem}:
 z^4 + 38*z^3 + 95*z^2 + 95*z

source

To compute signature Gröbner bases use

AlgebraicSolving.sig_groebner_basis — Method

function siggroebnerbasis(sys::Vector{T}; infolevel::Int=0, degbound::Int=0, modord::Symbol=:POT) 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 module order mod_ord underlying the computation. 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: If mod_ord == :DPOT then 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: Compute a full Gröbner basis if 0 otherwise only up to degree degbound.
mod_ord::Symbol=:DPOT: The module monomial order underlying the computation, either :POT (position-over-term, default) or :DPOT (degree-position-over-term) .

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), FqMPolyRingElem[x1, x2, x3, x4])

julia> F = cyclic(R)
FqMPolyRingElem[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 = homogenize(F.gens)
4-element Vector{FqMPolyRingElem}:
 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, mod_ord = :DPOT)
7-element Vector{Tuple{Tuple{Int64, FqMPolyRingElem}, FqMPolyRingElem}}:
 ((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