Crate groebner 

Groebner bases for multivariate polynomial ideals.

• groebner_basis_f4: F4 over any F4Field, with a fast dense modular path for PrimeField and Zp.
• groebner_basis, groebner_basis_incremental, groebner_basis_with_strategy and groebner_basis_parallel: Buchberger over any Field.
• Ideal: normal forms, membership, elimination, dimension, radical membership and change of order via fglm(), and membership certificates via Ideal::lift.
• PolynomialRing: parsing and formatting with named variables under any MonomialOrder.
• RationalFunction: coefficients in Q(a) for systems with one symbolic parameter.

F4 over a prime field

use groebner::{groebner_basis_f4, is_groebner_basis, 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)?;
assert!(is_groebner_basis(&basis));

Runtime modulus

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

let ring = PolynomialRing::<Zp>::with_modulus(["x", "y"], MonomialOrder::Lex, 1_000_003)?;
let basis = groebner_basis_f4(ring.parse_many("x^2 - y; x*y - 1")?, true)?;
assert_eq!(basis.len(), 2);

Ideals and change of order

use groebner::{Ideal, MonomialOrder, PolynomialRing};
use num_rational::BigRational;

let ring = PolynomialRing::<BigRational>::new(["x", "y"], MonomialOrder::GRevLex)?;
let ideal = Ideal::new(ring.parse_many("x^2 + y^2 - 1; x - y")?)?;
assert_eq!(ideal.vector_space_dimension(), Some(2));
let lex = ideal.change_order(MonomialOrder::Lex)?;
assert!(lex.contains(&ring.parse("2*y^2 - 1")?));

Re-exports

pub use modular::RationalOptions;

pub use modular::groebner_basis_f4_rational;

pub use modular::groebner_basis_f4_rational_with;

pub use f4::F4Field;

pub use f4::Reducers;

pub use f4::SparseRow;

pub use f4::groebner_basis_f4;

pub use fglm::fglm;

pub use fglm::is_zero_dimensional;

pub use fglm::standard_monomials;

pub use grebauer_moller::filter_gm_pairs;

pub use groebner::GroebnerError;

pub use groebner::SelectionStrategy;

pub use groebner::groebner_basis;

pub use groebner::groebner_basis_incremental;

pub use groebner::groebner_basis_with_strategy;

pub use groebner::is_groebner_basis;

pub use groebner::groebner_basis_parallel;

pub use groebner::is_groebner_basis_parallel;

pub use ideal::Ideal;

pub use lift::LiftBasis;

pub use lift::verify_lift;

pub use polynomial::PolynomialExt;

pub use rational_function::RationalFunction;

pub use rational_function::specialize;

pub use ring::ParseCoefficient;

pub use ring::ParsePolynomialError;

pub use ring::PolynomialRing;

Modules

f4

F4 Groebner basis computation (Faugere) with Gebauer-Moller pair selection and dense delayed-reduction linear algebra over machine-word prime fields.

fglm

FGLM change of ordering for zero-dimensional ideals.

finite_field

Prime fields supplied by polycore.

grebauer_moller

The selection strategy of Gebauer and Möller

groebner

Buchberger’s algorithm and basis utilities.

ideal

Ideals represented by a reduced Groebner basis.

lift

Ideal membership certificates via Buchberger’s algorithm with cofactor tracking.

modular

Multi-modular reconstruction of a reduced rational F4 basis.

monomial

Monomials and orders supplied by polycore.

polynomial

Groebner-specific operations on polycore polynomials.

rational_function

The field Q(a) of rational functions in one parameter.

ring

Polynomial ring helpers for parsing and formatting user-facing polynomials.

sugar

Sugar strategy for Groebner basis computation

Structs

Fp

An element of GF(p) for a prime p < 2^64 chosen at runtime.

Gf

An element of GF(P) for a prime P fixed at compile time.

Monomial

An exponent vector in one shared allocation, with its total degree cached.

Poly

A sparse multivariate polynomial: nonzero terms in strictly descending order.

Polynomial

A sparse multivariate polynomial: nonzero terms in strictly descending order.

PrimeField

An element of GF(P) for a prime P fixed at compile time.

PrimeFieldParseError

Ring

Variable names and an order: enough to read and write polynomials.

Zp

An element of GF(p) for a prime p < 2^64 chosen at runtime.

Enums

MonomialOrder

A monomial order on exponent vectors, variable 0 most significant.

Order

A monomial order on exponent vectors, variable 0 most significant.

Traits

Field

A field given by its operators. Every type with these operations is one, so BigRational, crate::Fp, crate::Gf and user extensions such as Q(sqrt(m)) need no wrapper.

Modular

A prime field of word-sized residues, for code that drops to bare u64 arithmetic in modp on its inner loops.

ModularField

A prime field of word-sized residues, for code that drops to bare u64 arithmetic in modp on its inner loops.

Type Aliases

Term