Groebner.jl

Groebner.jl is a package for fast and generic Gröbner bases computations based on Faugère's F4 algorithm^[1] written in Julia.

Installation

To install Groebner.jl, run the following in the Julia REPL:

using Pkg; Pkg.add("Groebner")

See Interface for a description of all exported functions. For a quick introduction to Groebner bases we refer to Tutorials. Meanwhile, below are simple examples.

Examples

Currently, polynomials from AbstractAlgebra.jl, DynamicPolynomials.jl, and Nemo.jl are supported as input.

with AbstractAlgebra.jl

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

using AbstractAlgebra

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

and compute the Groebner 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 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.

with DynamicPolynomials.jl

We will compute the basis of the noon-2 system^[2]

using DynamicPolynomials

@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}, Int64}}:
 10x2 - 10x1 - 11x2² + 11x1²
 110 - 121x2 - 100x2² + 100x1x2 + 110x2³
 10 - 11x1 + 10x1x2²

Contacts

This library is maintained by Alexander Demin (asdemin_2@edu.hse.ru).

Acknowledgement

We would like to acknowledge Jérémy Berthomieu, Christian Eder, and Mohab Safey El Din as this library is inspired by their work "msolve: A Library for Solving Polynomial Systems"^[3]. We are also grateful to The Max Planck Institute for Informatics and The MAX team at l'X for providing computational resources.

Special thanks goes to Vladimir Kuznetsov for providing the sources of his F4 implementation.