Struct SparseMultivariatePolynomial 

pub struct SparseMultivariatePolynomial<D: Domain, O: MonomialOrder = Grevlex> {
    pub order: O,
    /* private fields */
}

A sparse multivariate polynomial with coefficients in a domain D and monomial ordering O.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::sparse::Grevlex;
use ocas_poly::SparseMultivariatePolynomial;

let domain = IntegerDomain;
let p = SparseMultivariatePolynomial::<IntegerDomain, Grevlex>::from_terms(
    domain,
    2,
    vec![(vec![1, 0], Integer::from(2)), (vec![0, 1], Integer::from(3))],
);
let q = SparseMultivariatePolynomial::<IntegerDomain, Grevlex>::from_terms(
    domain,
    2,
    vec![(vec![1, 0], Integer::from(1)), (vec![0, 0], Integer::from(1))],
);
let r = p.mul(&q);
assert_eq!(r.coeff(&[1, 0]), Integer::from(2));
assert_eq!(r.coeff(&[0, 1]), Integer::from(3));
assert_eq!(r.coeff(&[2, 0]), Integer::from(2));

Fields

order: O

The monomial ordering used for leading-term and sorting operations.

Implementations

impl<D: Domain, O: MonomialOrder> SparseMultivariatePolynomial<D, O>

pub fn new(domain: D, n_vars: usize) -> Self

Create the zero polynomial in n_vars variables over domain with the default monomial ordering.

pub fn new_with_order(domain: D, n_vars: usize, order: O) -> Self

Create the zero polynomial with an explicit monomial ordering.

Example

use ocas_domain::IntegerDomain;
use ocas_poly::sparse::{SparseMultivariatePolynomial, WeightOrder};

let order = WeightOrder::from_slice(&[2, 1]);
let p = SparseMultivariatePolynomial::<_, WeightOrder>::new_with_order(
    IntegerDomain, 2, order,
);
assert_eq!(p.n_vars(), 2);

pub fn from_terms( domain: D, n_vars: usize, terms: Vec<(Vec<usize>, D::Element)>, ) -> Self

Create a polynomial from a list of (exponent vector, coefficient) pairs.

Zero coefficients and empty terms are dropped automatically.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::sparse::Grevlex;
use ocas_poly::SparseMultivariatePolynomial;

let domain = IntegerDomain;
let p = SparseMultivariatePolynomial::<IntegerDomain, Grevlex>::from_terms(
    domain,
    2,
    vec![(vec![1, 0], Integer::from(2)), (vec![0, 1], Integer::from(3))],
);
assert_eq!(p.n_terms(), 2);
assert_eq!(p.coeff(&[1, 0]), Integer::from(2));

pub fn domain(&self) -> &D

Return a reference to the coefficient domain.

pub fn n_vars(&self) -> usize

Return the number of variables.

pub fn n_terms(&self) -> usize

Return the number of non-zero terms.

pub fn is_zero(&self) -> bool

Return whether this is the zero polynomial.

pub fn terms_ref(&self) -> &HashMap<SmallVec<[usize; 4]>, D::Element>

Return a reference to the internal term map (exponent → coefficient).

pub fn set_term_external(&mut self, exp: Vec<usize>, coeff: D::Element)

Set the coefficient of a monomial (public version of set_term). Zero coefficients remove the term.

pub fn total_degree(&self) -> Option<usize>

Return the total degree, or None for the zero polynomial.

pub fn coeff(&self, exp: &[usize]) -> D::Element

Return the coefficient of the given monomial, or zero if absent.

pub fn zero(&self) -> Self

Return the zero polynomial with the same shape.

pub fn one(&self) -> Self

Return the constant polynomial 1 over the same shape.

pub fn neg(&self) -> Self

Return the negation of this polynomial.

pub fn add(&self, other: &Self) -> Self

Add another polynomial.

Panics if the polynomials have different numbers of variables.

pub fn sub(&self, other: &Self) -> Self

Subtract another polynomial.

Panics if the polynomials have different numbers of variables.

pub fn mul_scalar(&self, scalar: &D::Element) -> Self

Multiply by a scalar coefficient.

pub fn mul(&self, other: &Self) -> Self

Multiply two polynomials.

Panics if the polynomials have different numbers of variables.

pub fn sorted_terms(&self) -> Vec<(&SmallVec<[usize; 4]>, &D::Element)>

Return the terms sorted according to the monomial ordering.

pub fn leading_term(&self) -> Option<(&SmallVec<[usize; 4]>, &D::Element)>

Return the leading term (exponent_vector, coefficient) or None for the zero polynomial.

This scans the HashMap in O(n) without allocating — faster than sorted_terms() for repeated calls during reduction.

pub fn leading_monomial(&self) -> Option<&SmallVec<[usize; 4]>>

Return the leading monomial (exponent vector) or None.

pub fn leading_coeff(&self) -> Option<&D::Element>

Return the leading coefficient or None.

pub fn mul_monomial(&self, exp: &[usize]) -> Self

Multiply every term’s exponent vector by exp element-wise.

Panics if exp.len() != self.n_vars.

pub fn reduce(&self, basis: &[Self]) -> Self

Reduce self by the given basis (a list of polynomials).

Implements multivariate polynomial division: repeatedly look for a basis element whose leading monomial divides the current leading monomial, subtract the appropriate multiple, or else move the leading term into the remainder. Requires that div on the domain succeeds (i.e. the domain is effectively a field).

pub fn spoly(&self, other: &Self) -> Self

Compute the S-polynomial of self and other:

S(f, g) = f·lc(g)·x^(lcm-lm(f)) - g·lc(f)·x^(lcm-lm(g))

pub fn content(&self) -> D::Element

where D: EuclideanDomain,

Compute the content: the GCD of all coefficients.

For the zero polynomial the content is zero.

Example

use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::SparseMultivariatePolynomial;
use ocas_poly::Lex;

let p = SparseMultivariatePolynomial::<_, Lex>::from_terms(
    IntegerDomain, 1,
    vec![(vec![2], Integer::from(6)), (vec![1], Integer::from(9)), (vec![0], Integer::from(3))],
);
assert_eq!(p.content(), Integer::from(3));

pub fn primitive_part(&self) -> Self

where D: EuclideanDomain,

Return the primitive part: self / content.

The result has content 1 (or is zero).

Example

use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::SparseMultivariatePolynomial;
use ocas_poly::Lex;

let p = SparseMultivariatePolynomial::<_, Lex>::from_terms(
    IntegerDomain, 1,
    vec![(vec![2], Integer::from(6)), (vec![0], Integer::from(3))],
);
let pp = p.primitive_part();
// After dividing by content=3: 2*x^2 + 1
assert_eq!(pp.coeff(&[2]), Integer::from(2));
assert_eq!(pp.coeff(&[0]), Integer::from(1));

pub fn div_exact(&self, divisor: &Self) -> Self

Divide this polynomial by another, assuming the division is exact (no remainder).

Each term of self is divided by the corresponding factor from divisor. This is used in rational-function canonicalization where the GCD is known to divide both numerator and denominator.

Panics

Panics if the division is not exact.

pub fn degree_in(&self, var_index: usize) -> usize

Return the degree of this polynomial in the given variable.

Returns 0 for the zero polynomial (by convention) or if the variable does not appear.

pub fn coeff_of_var_pow(&self, var_index: usize, pow: usize) -> Self

Return the coefficient polynomial of x_var^pow: the sum of all terms whose exponent in var_index equals pow, with that exponent zeroed out. The result has the same number of variables and does not depend on var_index.

pub fn leading_coeff_in(&self, var_index: usize) -> Self

Return the leading coefficient when this polynomial is viewed as a univariate polynomial in var_index. The result is a polynomial in the remaining variables (same n_vars, exponent of var_index is 0).

pub fn derivative(&self, var_index: usize) -> Self

Compute the formal partial derivative with respect to var_index.

pub fn taylor_coefficients(&self, var_index: usize, a: &D::Element) -> Vec<Self>

Compute the Taylor coefficients in variable var_index around a: f = Σ_j t_j · (x_var - a)^j where each t_j does not depend on var_index (its exponent is zeroed).

Returns t_0, t_1, ..., t_d with d = degree_in(var_index).

pub fn drop_main_var(&self) -> Self

Drop variable 0, which must not occur in any term. Returns a polynomial in n_vars - 1 variables with indices shifted down.

Panics in debug builds if variable 0 occurs with a non-zero exponent.

pub fn embed_new_main(&self) -> Self

Embed into one more variable by inserting a new variable 0 with exponent 0 (all existing variable indices shift up by one).

pub fn drop_variable(&self, var_index: usize) -> Self

Drop variable var_index from the polynomial, producing a polynomial in one fewer variable. Only safe when no term has a nonzero exponent for var_index (otherwise those terms are silently dropped).

pub fn extend_vars(&self, new_n_vars: usize) -> Self

Extend to new_n_vars variables by appending zero exponents.

Requires new_n_vars >= self.n_vars. Existing variable indices are unchanged; new variables are appended at the end.

pub fn permute_variables(&self, perm: &[usize]) -> Self

Permute variables: the result’s exponent at position i is the old exponent at position perm[i]. perm must be a permutation of 0..n_vars.

pub fn checked_div_exact(&self, divisor: &Self) -> Option<Self>

Divide this polynomial by divisor, returning the quotient only if the division is exact (zero remainder).

pub fn eval_keep(&self, var_index: usize, value: &D::Element) -> Self

Evaluate variable var_index at value while keeping the total number of variables unchanged (the variable disappears from the support but all indices are preserved).

This is the substitution used by multivariate Hensel lifting, where variable positions must stay fixed across recursion levels.

pub fn max_exp(&self) -> Option<&SmallVec<[usize; 4]>>

Return the exponent vector of the leading monomial, or None for zero.

This is an alias for leading_monomial that matches the Symbolica naming convention used in the F4 algorithm.

pub fn max_coeff(&self) -> Option<&D::Element>

Return the leading coefficient, or None for zero.

This is an alias for leading_coeff that matches the Symbolica naming convention used in the F4 algorithm.

pub fn exponents_iter(&self) -> impl Iterator<Item = &SmallVec<[usize; 4]>>

Iterate over all exponent vectors in sorted order (descending by the monomial ordering).

The F4 algorithm uses this to enumerate every monomial in a polynomial for symbolic preprocessing.

pub fn make_monic_inplace(&mut self) -> bool

Divide every term by the leading coefficient, making the polynomial monic. Returns false if the polynomial is zero or the leading coefficient has no inverse.

pub fn zero_with_capacity(&self, _cap: usize) -> Self

Create a zero polynomial with the same domain and variable count.

This is identical to zero but named to match the Symbolica convention used in F4 code.

pub fn append_monomial(&mut self, coeff: D::Element, exp: &[usize])

Append a single monomial term coeff * x^exp.

If the monomial already exists, the coefficients are summed. Zero coefficients remove the term.

pub fn eval(&self, var_index: usize, value: &D::Element) -> Self

Evaluate the polynomial by substituting value for variable var_index.

Returns a polynomial in one fewer variable (all remaining variables keep their relative order). If var_index is the only variable, the result is a zero-variable (constant) polynomial.

Example

use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::SparseMultivariatePolynomial;
use ocas_poly::Lex;

let p = SparseMultivariatePolynomial::<_, Lex>::from_terms(
    IntegerDomain, 2,
    vec![
        (vec![1, 1], Integer::from(1)), // x*y
        (vec![0, 1], Integer::from(2)), // 2*y
    ],
);
// Substitute x=3: result = 3*y + 2*y = 5*y
let r = p.eval(0, &Integer::from(3));
assert_eq!(r.coeff(&[1]), Integer::from(5));

impl SparseMultivariatePolynomial<IntegerDomain, Lex>

pub fn factor(&self) -> Vec<(Self, usize)>

Factor this bivariate integer polynomial into irreducible factors with multiplicities.

With a constant leading coefficient in $x$ the polynomial is treated as univariate in $x$ with coefficients in $\mathbb{Z}[y]$ and factored via Wang’s bivariate Hensel-lifting algorithm. With a non-constant leading coefficient the general EEZ path with Wang leading-coefficient imposition (p-adic coefficient Hensel lifting) is used instead.

Example

use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::SparseMultivariatePolynomial;
use ocas_poly::Lex;

// (x^2 + y + 1)(x + y + 2)
let f = SparseMultivariatePolynomial::<_, Lex>::from_terms(
    IntegerDomain, 2,
    vec![
        (vec![3, 0], Integer::from(1)),
        (vec![2, 1], Integer::from(1)),
        (vec![2, 0], Integer::from(2)),
        (vec![1, 1], Integer::from(1)),
        (vec![1, 0], Integer::from(1)),
        (vec![0, 2], Integer::from(1)),
        (vec![0, 1], Integer::from(3)),
        (vec![0, 0], Integer::from(2)),
    ],
);
let factors = f.factor();
assert!(factors.len() >= 2);

impl SparseMultivariatePolynomial<FiniteField, Lex>

pub fn factor(&self) -> Vec<(Self, usize)>

Factor this multivariate polynomial over a prime finite field into irreducible factors with multiplicities.

Bivariate polynomials use the evaluation–Hensel path; polynomials in three or more variables use EEZ Hensel lifting. Both currently require the leading coefficient in the main variable to be a nonzero field constant.

Trait Implementations

impl<D: Clone + Domain, O: Clone + MonomialOrder> Clone for SparseMultivariatePolynomial<D, O>

where D::Element: Clone,

fn clone(&self) -> SparseMultivariatePolynomial<D, O>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<D: Debug + Domain, O: Debug + MonomialOrder> Debug for SparseMultivariatePolynomial<D, O>

where D::Element: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<D: Eq + Domain, O: Eq + MonomialOrder> Eq for SparseMultivariatePolynomial<D, O>

where D::Element: Eq,

impl<D: PartialEq + Domain, O: PartialEq + MonomialOrder> PartialEq for SparseMultivariatePolynomial<D, O>

where D::Element: PartialEq,

fn eq(&self, other: &SparseMultivariatePolynomial<D, O>) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<D: PartialEq + Domain, O: PartialEq + MonomialOrder> StructuralPartialEq for SparseMultivariatePolynomial<D, O>

where D::Element: PartialEq,