Groebner.jl — Fast Groebner bases in Julia

Groebner.jl is a package for computing Gröbner bases written in Julia. Groebner.jl implements the Faugère's F4 algorithm and multi-modular computation.

Installation

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

using Pkg; Pkg.add("Groebner")

Features

Groebner.jl features:

Gröbner basis over integers modulo a prime and over the rationals
Gröbner trace algorithms
Multi-threading

See Interface page for a list of all exported functions.

Examples

As input, Groebner.jl supports polynomials from AbstractAlgebra.jl, DynamicPolynomials.jl, and Nemo.jl.

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) = polynomial_ring(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

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}, Rational{BigInt}}}:
 10//11x2 - 10//11x1 - x2² + x1²
 1//1 - 11//10x2 - 10//11x2² + 10//11x1x2 + x2³
 1//1 - 11//10x1 + x1x2²

Contacts

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

We would like to acknowledge the developers of the msolve library (https://msolve.lip6.fr/), as several components of Groebner.jl were adapted from msolve. In our F4 implementation, we adapt and adjust the code of monomial hashtable, critical pair handling and symbolic preprocessing, and linear algebra from msolve. The source code of msolve is available at https://github.com/algebraic-solving/msolve.

We thank Vladimir Kuznetsov for helpful discussions and providing the sources of his F4 implementation.

We are grateful to The Max Planck Institute for Informatics and The MAX team at l'X for providing computational resources.