Gröbner Basis

An optimized Rust implementation of the F4 and Buchberger algorithms for computing Gröbner bases. It achieves SOTA performance on standard benchmarks over prime fields and the rationals, using parallel sparse linear algebra, SIMD row reduction, and multi-modular rational reconstruction.

Examples:

• Buchberger example
• F4 example

Usage

cargo add groebner

Parse polynomials with named variables under a monomial order and compute a reduced Gröbner basis with F4 (over PrimeField<P>, Zp or BigRational):

use groebner::{groebner_basis_f4, MonomialOrder, PolynomialRing, PrimeField};

let ring = PolynomialRing::<PrimeField<32003>>::new(["x", "y"], MonomialOrder::GRevLex)?;
let polys = ring.parse_many("x^2 - y; x*y - 1")?;
let basis = groebner_basis_f4(polys, true)?;
for p in &basis {
    println!("{}", ring.format(p)?);
}
# Ok::<(), Box<dyn std::error::Error>>(())

See the API documentation for Buchberger, runtime primes, ideals, lift certificates, monomial orders, and parametric coefficients.

Enable the mimalloc feature for maximal performance. It installs mimalloc as the global allocator, so leave it off if your binary already sets one.

groebner = { version = "0.6", features = ["mimalloc"] }

Python

Use the ctypes wrapper over the C library. Polynomials are strings, over Q by default or GF(p) with modulus:

from groebner import Order, Ring, contains, groebner_basis

groebner_basis(["x^2 + y^2 - 1", "x - y"], order=Order.LEX)  # ['x - y', 'y^2 - 1/2']
contains("2*y^2 - 1", ["x^2 + y^2 - 1", "x - y"])  # True

ring = Ring(["x", "y"], Order.LEX, modulus=32003)
ring.groebner_basis(["x^2 - y", "x*y - 1"])  # ['x + 32002*y^2', 'y^3 + 32002']

To depend on it from a pyproject.toml (builds from source, requires a Rust toolchain):

[project]
dependencies = [
    "groebner @ git+https://github.com/sdiehl/groebner.git@v0.7.0",
]

Or with uv:

uv add git+https://github.com/sdiehl/groebner --tag v0.7.0

which records it in pyproject.toml as:

[project]
dependencies = ["groebner"]

[tool.uv.sources]
groebner = { git = "https://github.com/sdiehl/groebner", tag = "v0.7.0" }

Benchmarks

Reduced basis with groebner_basis_f4 over GF(32003) in GRevLex, on Apple M5 silicon (10 cores).

System	Basis size	Time
chandra12	2048	0.41 s
chandra13	4096	1.42 s
cyclic8	372	0.18 s
cyclic9	1344	4.98 s
eco12	743	0.25 s
eco13	1465	0.84 s
eco14	2852	4.35 s
henrion7	415	0.35 s
henrion8	2344	24.1 s
katsura11	1050	0.47 s
katsura12	2091	2.12 s
katsura13	4140	11.8 s
noon9	3682	1.54 s
noon10	10273	8.64 s
reimer7	227	0.14 s
reimer8	612	1.54 s

With a runtime modulus through Zp, same settings, by size of the prime.

System	32003	2^31 - 1	2^62 - 57	2^63 - 25
cyclic8	0.18 s	0.21 s	0.25 s	0.30 s
katsura11	0.48 s	0.60 s	0.74 s	0.97 s
noon9	1.56 s	1.67 s	1.80 s	1.99 s
reimer8	1.59 s	1.75 s	2.00 s	2.52 s

Over the rationals with BigRational coefficients, same settings.

System	Basis size	Time
cyclic8	372	1.68 s
eco12	743	1.37 s
katsura9	272	0.23 s
katsura10	537	1.68 s
noon9	3682	3.22 s
reimer7	227	0.67 s

Inputs are in benches/data.

Test Suite

cargo test
cargo bench --features mimalloc

The test suite is the full list of known Gröbner bases for a variety of large multivariate polynomial systems from several textbooks and some trusted Mathematica generated corpus. Both the Rust algo implementations have to correctly produce the same textbook outputs and Mathematica for all inputs, up to re-ordering.

License

MIT Licensed. Copyright 2024-2026 Stephen Diehl. See LICENSE for details.