Gröbner bases

Introduction

AlgebraicSolving allows to compute Gröbner bases for input generators over prime fields of characteristic smaller $2^{31}$, over the rationals w.r.t. the degree reverse lexicographical monomial order and over fields of rational fractions of polynomial rings 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.
worker_pool::Union{Nothing,AbstractWorkerPool}=nothing: if not nothing, run the core Gröbner-basis array computation on a worker from this pool.
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

AlgebraicSolving.groebner_basis — Method

groebner_basis(I::ParametricIdeal{K}; <keyword arguments>) -> Vector{Generic.MPoly{FracFieldElem{QQMPolyRingElem}}}

Computes a parametric Gröbner basis of the parametric ideal I w.r.t. the degree reverse lexicographic ordering. The Gröbner basis is computed by evaluating the ideal at a number of parameter values and interpolating the coefficients of the resulting Gröbner bases.

Arguments

retry::Int=10: the maximum number of consecutive failures allowed when computing the Gröbner basis or interpolating the coefficients.
nr_thrds::Int=1: the number of threads to use for parallel computations.
worker_pool::AbstractWorkerPool=default_worker_pool(): the worker pool to use for parallel computations.
show_progress::Bool=false: whether to show a progress bar while computing the Gröbner basis.

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.
worker_pool::Union{Nothing,AbstractWorkerPool}=nothing: run the Gröbner basis computation on a worker from the given pool, if not nothing.
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

sig_groebner_basis(sys::Vector{T}; info_level::Int=0, degbound::Int=0, mod_ord::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

AlgebraicSolving also allows the computation of multiplication matrices of polynomials modulo polynomial ideals. For a polynomial ideal $I$ in a polynomial ring $R$ and a polynomial $g \in R$, this is a matrix representing the linear map sending an element $f\in R / I$ to $gf \in R/I$.

AlgebraicSolving.multiplication_matrix — Method

multiplication_matrix(gb::Vector{T}, b::Vector{T}, g::T) -> MatElem

Computes the multiplication matrix associated with the polynomial g with respect to the Groebner basis gb and the monomial basis b.

source

AlgebraicSolving.multiplication_matrix — Method

multiplication_matrix(I::ParametricIdeal{K}, g::MPoly{K}; <keyword arguments>) -> MatSpaceElem{K}

Computes the parametric multiplication matrix associated with the polynomial g with respect to the parametric ideal I. The multiplication matrix is computed by evaluating the ideal at a number of parameter values and interpolating the coefficients of the resulting multiplication matrices.

Arguments

retry::Int=10: the maximum number of consecutive failures allowed when computing the multiplication matrix or interpolating the coefficients.
nr_thrds::Int=1: the number of threads to use for parallel computations.
worker_pool::AbstractWorkerPool=default_worker_pool(): the worker pool to use for parallel computations.
show_progress::Bool=false: whether to show a progress bar while computing the multiplication matrix.

source