Examples

Groebner.jl supports polynomials from the following frontends:

• AbstractAlgebra.jl
• Nemo.jl
• DynamicPolynomials.jl

Additionally, Groebner.jl has a low-level entry point that accepts raw polynomial data.

Using AbstractAlgebra.jl

First, we import AbstractAlgebra.jl. Then, we create an array of polynomials over a finite field

using AbstractAlgebra

R, (x, y, z) = polynomial_ring(GF(2^31 - 1), ["x", "y", "z"])
polys = [x^2 + y + z, x*y + z];

2-element Vector{AbstractAlgebra.Generic.MPoly{AbstractAlgebra.GFElem{Int64}}}:
 x^2 + y + z
 x*y + z

and compute a Gröbner basis with the groebner command

using Groebner

basis = groebner(polys)

4-element Vector{AbstractAlgebra.Generic.MPoly{AbstractAlgebra.GFElem{Int64}}}:
 y^3 + y^2*z + z^2
 x*z + 2147483646*y^2 + 2147483646*y*z
 x*y + z
 x^2 + y + z

We can check if a set of polynomials forms a Gröbner basis

isgroebner(basis)

true

Groebner.jl also provides several monomial orderings. For example, we can eliminate z from the above system:

ordering = Lex(z) * DegRevLex(x, y)  # z > x, y
groebner(polys, ordering=ordering)

2-element Vector{AbstractAlgebra.Generic.MPoly{AbstractAlgebra.GFElem{Int64}}}:
 x^2 + 2147483646*x*y + y
 x*y + z

You can find more information on monomial orderings in Groebner.jl in Monomial orderings.

Using DynamicPolynomials.jl

Computing the Gröbner basis of some system:

using DynamicPolynomials, Groebner

@polyvar x1 x2
system = [10*x1*x2^2 - 11*x1 + 10,
        10*x1^2*x2 - 11*x2 + 10]

groebner(system)

3-element Vector{DynamicPolynomials.Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}, Rational{BigInt}}}:
 10//11x2 - 10//11x1 - x2² + x1²
 1//1 - 11//10x2 - 10//11x2² + 10//11x1x2 + x2³
 1//1 - 11//10x1 + x1x2²

Using Low-level interface

Some functions in the interface have a low-level entry point. Low-level functions accept and output ''raw'' exponent vectors and coefficients. This could be convenient when one does not want to depend on a frontend.

For example,

using Groebner

# define {x * y - 1, x^3 + 7 * y^2} modulo 65537 in DRL
ring = Groebner.PolyRing(2, Groebner.DegRevLex(), 65537)
monoms = [ [[1, 1], [0, 0]], [[3, 0], [0, 2]] ]
coeffs = [ [    1,     -1 ], [    1,      7 ] ]

# compute a GB
gb_monoms, gb_coeffs = Groebner.groebner(ring, monoms, coeffs)

(Vector{Vector{UInt32}}[[[0x00000001, 0x00000001], [0x00000000, 0x00000000]], [[0x00000000, 0x00000003], [0x00000002, 0x00000000]], [[0x00000003, 0x00000000], [0x00000000, 0x00000002]]], Vector{UInt32}[[0x00000001, 0x00010000], [0x00000001, 0x00004925], [0x00000001, 0x00000007]])

The list of functions that provide a low-level entry point: groebner, normalform, isgroebner, groebner_learn, groebner_apply.

Low-level functions may be faster than their user-facing analogues since they bypass data conversions. Low-level functions do not make any specific assumptions on input polynomials, that is, all of these cases are correctly handled: unsorted monomials, non-normalized coefficients, duplicate terms, aliasing memory.

Generic coefficients

The implementation in Groebner.jl uses a generic type for coefficients. Hence, in theory, Groebner.jl can compute Gröbner bases over any type that behaves like a field.

For the following ground fields Groebner.jl runs an efficient native implementation:

• integers modulo a prime,
• rationals numbers.

For other ground fields, a possibly slower generic fallback is used. In this case, coefficients of polynomials are treated as black-boxes which implement field operations: zero, one, inv, ==, +, *, -.

For example, we can compute a Gröbner basis over a univariate rational function field over a finite field:

using Groebner, AbstractAlgebra

R, t = GF(101)["t"]
ff = fraction_field(R)
_, (x, y) = ff["x","y"]

sys = [(t//t+1)*x*y - t^3, y^2 + t]

gb = groebner(sys)

2-element Vector{AbstractAlgebra.Generic.MPoly{AbstractAlgebra.Generic.FracFieldElem{AbstractAlgebra.Generic.Poly{AbstractAlgebra.GFElem{Int64}}}}}:
 y^2 + t
 x + 51*t^2*y

Many functions reuse the core implementation, so they can also be used over generic fields:

@assert isgroebner(gb)
normalform(gb, x*y)

Computing over floating point intervals

In the following example, we combine low-level interface and generic coefficients.

We are going to compute a basis of the hexapod system over tuples (Z_p, Interval): each coefficient is treated as a pair, the first coordinate is a finite field element used for zero testing, and the second coordinate is a floating point interval with some fixed precision, the payload. For floating point arithmetic, we will be using MPFI.jl.

using Pkg;
Pkg.add(url="https://gitlab.inria.fr/ckatsama/mpfi.jl")

import Base: +, -, *, zero, iszero, one, isone, inv
using AbstractAlgebra, Groebner, MPFI

PRECISION = 1024 # For MPFI intervals

struct Zp_And_FloatInterval{Zp, FloatInterval}
    a::Zp
    b::FloatInterval
end

# Pretend it is a field and hakuna matata
+(x::Zp_And_FloatInterval, y::Zp_And_FloatInterval) = Zp_And_FloatInterval(x.a + y.a, x.b + y.b)
*(x::Zp_And_FloatInterval, y::Zp_And_FloatInterval) = Zp_And_FloatInterval(x.a * y.a, x.b * y.b)
-(x::Zp_And_FloatInterval, y::Zp_And_FloatInterval) = Zp_And_FloatInterval(x.a - y.a, x.b - y.b)
zero(x::Zp_And_FloatInterval) = Zp_And_FloatInterval(zero(x.a), zero(x.b))
one(x::Zp_And_FloatInterval) = Zp_And_FloatInterval(one(x.a), one(x.b))
inv(x::Zp_And_FloatInterval) = Zp_And_FloatInterval(inv(x.a), inv(x.b))
iszero(x::Zp_And_FloatInterval) = iszero(x.a)
isone(x::Zp_And_FloatInterval) = isone(x.a)

@info "Computing Hexapod over QQ"
c_zp = Groebner.Examples.hexapod(k=AbstractAlgebra.GF(2^30+3));
c_qq = Groebner.Examples.hexapod(k=AbstractAlgebra.QQ);
@time gb_truth = groebner(c_qq);
gbcoeffs_truth = map(f -> collect(coefficients(f)), gb_truth);
@info "Coefficient size (in bits): $(maximum(f -> maximum(c -> log2(abs(numerator(c))) + log2(denominator(c)), f), gbcoeffs_truth))"

@info "Computing Hexapod over (Zp, Interval). Precision = $PRECISION bits"
ring = Groebner.PolyRing(nvars(parent(c_qq[1])), Groebner.DegRevLex(), 0, :generic); # Note :generic
exps = map(f -> collect(exponent_vectors(f)), c_zp);
cfs_qq = map(f -> collect(coefficients(f)), c_qq);
cfs_zp = map(f -> collect(coefficients(f)), c_zp);
cfs = map(f -> map(c -> Groebner.CoeffGeneric(Zp_And_FloatInterval(c[1], BigInterval(c[2], precision=PRECISION))), zip(f...)), zip(cfs_zp, cfs_qq));
@time gbexps, gbcoeffs = groebner(ring, exps, cfs);

to_inspect = gbcoeffs[end][end]
@info "
    Inspect one coefficient in the basis:
    Zp         = $(to_inspect.data.a)
    Interval   = $(to_inspect.data.b)
    Diam       = $(diam(to_inspect.data.b))
    Diam (rel) = $(diam_rel(to_inspect.data.b))"

# Sanity check
all_are_inside(x::Zp_And_FloatInterval, truth) = is_inside(BigInterval(truth; precision=PRECISION), x.b)
all_are_inside(x::Groebner.CoeffGeneric, truth) = all_are_inside(x.data, truth)
all_are_inside(x::AbstractVector, truth) = all(map(all_are_inside, x, truth))
@assert all_are_inside(gbcoeffs, gbcoeffs_truth)

# Max |midpoint - truth|
max_error(x::Zp_And_FloatInterval, y; rel=false) = abs(mid(x.b) - y) / ifelse(rel, max(abs(y), 0), 1)
max_error(x::Groebner.CoeffGeneric, y; rel=false) = max_error(x.data, y; rel=rel)
max_error(x::AbstractVector, y::AbstractVector; rel=false) = maximum(map(f -> max_error(f...; rel=rel), zip(x, y)))
@info "
    Max error      : $(max_error(gbcoeffs, gbcoeffs_truth))
    Max error (rel): $(max_error(gbcoeffs, gbcoeffs_truth; rel=true))"

# Max diameter
max_diam(x::Zp_And_FloatInterval; rel=false) = ifelse(rel, diam_rel(x.b), diam(x.b))
max_diam(x::Groebner.CoeffGeneric; rel=false) = max_diam(x.data; rel=rel)
max_diam(x::AbstractVector; rel=false) = maximum(map(f -> max_diam(f; rel=rel), x))
@info "
    Max diam      : $(max_diam(gbcoeffs))
    Max diam (rel): $(max_diam(gbcoeffs; rel=true))"

     Cloning git-repo `https://gitlab.inria.fr/ckatsama/mpfi.jl`
    Updating git-repo `https://gitlab.inria.fr/ckatsama/mpfi.jl`
    Updating registry at `~/.julia/registries/General.toml`
   Resolving package versions...
   Installed MPFI_jll ─ v1.5.6+0
  Installing 1 artifacts
   Installed artifact MPFI       50.0 KiB
    Updating `~/work/Groebner.jl/Groebner.jl/docs/Project.toml`
  [e50a78b8] + MPFI v0.0.2 `https://gitlab.inria.fr/ckatsama/mpfi.jl#main`
    Updating `~/work/Groebner.jl/Groebner.jl/docs/Manifest.toml`
  [e50a78b8] + MPFI v0.0.2 `https://gitlab.inria.fr/ckatsama/mpfi.jl#main`
  [e8b5fb6c] + MPFI_jll v1.5.6+0
Precompiling packages...
    717.6 ms  ✓ MPFI_jll
    787.0 ms  ✓ MPFI
  2 dependencies successfully precompiled in 4 seconds. 99 already precompiled.
[ Info: Computing Hexapod over QQ
 10.758271 seconds (22.70 M allocations: 1.312 GiB, 5.24% gc time, 69.36% compilation time: 28% of which was recompilation)
[ Info: Coefficient size (in bits): 26417.51221660290345963338930851770671711863223901550154467730075030408186732383
[ Info: Computing Hexapod over (Zp, Interval). Precision = 1024 bits
  4.389018 seconds (13.36 M allocations: 1.230 GiB, 4.49% gc time, 64.66% compilation time)
┌ Error: Exception while generating log record in module Main at examples.md:159
│   exception =
│    MethodError: no method matching convert(::Type{DataType}, ::BigFloat)
│    The function `convert` exists, but no method is defined for this combination of argument types.
│
│    Closest candidates are:
│      convert(!Matched::Type{Any}, ::Any)
│       @ Core boot.jl:346
│      convert(::Type{T}, !Matched::T) where T
│       @ Core boot.jl:347
│
│    Stacktrace:
│      [1] FieldError(type::BigFloat, field::Symbol)
│        @ Core ./boot.jl:454
│      [2] setproperty!
│        @ ./mpfr.jl:209 [inlined]
│      [3] string
│        @ ~/.julia/packages/MPFI/u0V55/src/MPFI.jl:963 [inlined]
│      [4] print
│        @ ~/.julia/packages/MPFI/u0V55/src/MPFI.jl:1008 [inlined]
│      [5] print_to_string(::String, ::AbstractAlgebra.GFElem{Int64}, ::String, ::MPFI.BigInterval, ::String, ::BigFloat, ::String, ::BigFloat)
│        @ Base ./strings/io.jl:151
│      [6] string(::String, ::AbstractAlgebra.GFElem{Int64}, ::String, ::Vararg{Any})
│        @ Base ./strings/io.jl:193
│      [7] top-level scope
│        @ examples.md:395
│      [8] macro expansion
│        @ logging/logging.jl:385 [inlined]
│      [9] eval(m::Module, e::Any)
│        @ Core ./boot.jl:489
│     [10] #61
│        @ ~/.julia/packages/Documenter/eoWm2/src/expander_pipeline.jl:856 [inlined]
│     [11] cd(f::Documenter.var"#61#62"{Module, Expr}, dir::String)
│        @ Base.Filesystem ./file.jl:112
│     [12] (::Documenter.var"#59#60"{Documenter.Page, Module, Expr})()
│        @ Documenter ~/.julia/packages/Documenter/eoWm2/src/expander_pipeline.jl:855
│     [13] (::IOCapture.var"#12#13"{Type{InterruptException}, Documenter.var"#59#60"{Documenter.Page, Module, Expr}, IOContext{Base.PipeEndpoint}, IOContext{Base.PipeEndpoint}, Base.PipeEndpoint, Base.PipeEndpoint})()
│        @ IOCapture ~/.julia/packages/IOCapture/Y5rEA/src/IOCapture.jl:170
│     [14] with_logstate(f::IOCapture.var"#12#13"{Type{InterruptException}, Documenter.var"#59#60"{Documenter.Page, Module, Expr}, IOContext{Base.PipeEndpoint}, IOContext{Base.PipeEndpoint}, Base.PipeEndpoint, Base.PipeEndpoint}, logstate::Base.CoreLogging.LogState)
│        @ Base.CoreLogging ./logging/logging.jl:540
│     [15] with_logger(f::Function, logger::Base.CoreLogging.ConsoleLogger)
│        @ Base.CoreLogging ./logging/logging.jl:651
│     [16] capture(f::Documenter.var"#59#60"{Documenter.Page, Module, Expr}; rethrow::Type, color::Bool, passthrough::Bool, capture_buffer::IOBuffer, io_context::Vector{Any})
│        @ IOCapture ~/.julia/packages/IOCapture/Y5rEA/src/IOCapture.jl:167
│     [17] runner(::Type{Documenter.Expanders.ExampleBlocks}, node::MarkdownAST.Node{Nothing}, page::Documenter.Page, doc::Documenter.Document)
│        @ Documenter ~/.julia/packages/Documenter/eoWm2/src/expander_pipeline.jl:854
│     [18] dispatch(::Type{Documenter.Expanders.ExpanderPipeline}, ::MarkdownAST.Node{Nothing}, ::Vararg{Any})
│        @ Documenter.Selectors ~/.julia/packages/Documenter/eoWm2/src/utilities/Selectors.jl:170
│     [19] expand(doc::Documenter.Document)
│        @ Documenter ~/.julia/packages/Documenter/eoWm2/src/expander_pipeline.jl:59
│     [20] runner(::Type{Documenter.Builder.ExpandTemplates}, doc::Documenter.Document)
│        @ Documenter ~/.julia/packages/Documenter/eoWm2/src/builder_pipeline.jl:224
│     [21] dispatch(::Type{Documenter.Builder.DocumentPipeline}, x::Documenter.Document)
│        @ Documenter.Selectors ~/.julia/packages/Documenter/eoWm2/src/utilities/Selectors.jl:170
│     [22] #89
│        @ ~/.julia/packages/Documenter/eoWm2/src/makedocs.jl:280 [inlined]
│     [23] withenv(::Documenter.var"#89#90"{Documenter.Document}, ::Pair{String, Nothing}, ::Vararg{Pair{String, Nothing}})
│        @ Base ./env.jl:265
│     [24] #87
│        @ ~/.julia/packages/Documenter/eoWm2/src/makedocs.jl:279 [inlined]
│     [25] cd(f::Documenter.var"#87#88"{Documenter.Document}, dir::String)
│        @ Base.Filesystem ./file.jl:112
│     [26] makedocs(; debug::Bool, format::Documenter.HTMLWriter.HTML, kwargs::@Kwargs{modules::Vector{Module}, sitename::String, doctest::Bool, linkcheck::Bool, checkdocs::Symbol, warnonly::Bool, pages::Vector{Pair{String, String}}})
│        @ Documenter ~/.julia/packages/Documenter/eoWm2/src/makedocs.jl:278
│     [27] macro expansion
│        @ ./timing.jl:689 [inlined]
│     [28] top-level scope
│        @ ~/work/Groebner.jl/Groebner.jl/docs/make.jl:353
│     [29] include(mod::Module, _path::String)
│        @ Base ./Base.jl:306
│     [30] exec_options(opts::Base.JLOptions)
│        @ Base ./client.jl:317
│     [31] _start()
│        @ Base ./client.jl:550
└ @ Main examples.md:159
┌ Info:
│     Max error      : 1.228864326279742133434060342410214649753730878890848130615480485662809941472111e-51
└     Max error (rel): 2.127849791509757036887182607381235177361098814152126217820831601897105585301116e-77
┌ Info:
│     Max diam      : 1.202460211377052991684279730262989280695122676646933719333198938473338220666243005911208907254489599815389991605688400764539497569401287751641248190538361586297178234457598088451411818969961772698669019572643689781706754158694087745157768440540233361634518715844476807816772233724409911900292268141779522198055e-132
└     Max diam (rel): 1.202460211377052991684279730262989280695122676646933719333198938473338220666243005911208907254489599815389991605688400764539497569401287751641248190538361586297178234457598088451411818969961772698669019572643689781706754158694087745157768440540233361634518715844476807816772233724409911900292268141779522198055e-132

However, if we lower MPFI precision to 256 bits, some of the intervals become NaN.