Function buchberger_algorithm

Source

pub fn buchberger_algorithm(
    generators: &[Expression],
    variables: &[Symbol],
    order: &MonomialOrder,
) -> MathResult<Vec<Expression>>

Expand description

Compute Gröbner basis using Buchberger’s algorithm

Implements Buchberger’s algorithm with optimizations:

Buchberger’s criteria for avoiding unnecessary S-polynomial computations
Efficient pair management using VecDeque (O(1) pop_front)
Early termination when pairs are relatively prime
Automatic basis reduction after main loop

The returned basis is auto-reduced: each polynomial is reduced with respect to all others in the basis, ensuring minimality.

§Algorithm

Start with initial polynomial generators
Maintain a queue of polynomial pairs to process
For each pair (f, g):
- Apply Buchberger’s criteria to skip unnecessary pairs
- Compute S-polynomial: S(f, g)
- Reduce S(f, g) modulo the current basis
- If remainder is non-zero, add to basis and generate new pairs
Auto-reduce the basis (each polynomial reduced by all others)
Remove any zero polynomials

§Arguments

generators - Initial generating set for the ideal
variables - Ordered list of variables
order - Monomial ordering to use

§Returns

Returns Ok(Vec<Expression>) containing the auto-reduced Gröbner basis, or Err(MathError::MaxIterationsReached) if the iteration limit is exceeded.

§Errors

Returns MathError::MaxIterationsReached if the algorithm does not converge within the maximum iteration limit (10,000 iterations). This may occur for very large or complex polynomial systems.

§Examples

use mathhook_core::{symbol, expr, Expression};
use mathhook_core::algebra::groebner::{buchberger_algorithm, MonomialOrder};

let x = symbol!(x);
let y = symbol!(y);
let f1 = Expression::add(vec![expr!(x^2), expr!(y^2), expr!(-1)]);
let f2 = expr!(x - y);
let gb = buchberger_algorithm(
    &vec![f1, f2],
    &vec![x, y],
    &MonomialOrder::Lex
).expect("Should converge");
assert!(!gb.is_empty());

buchberger_algorithm