Struct SparseMultivariatePolynomial

Source

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

Expand description

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));

Implementations§

Source §

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

Source

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

Create the zero polynomial in n_vars variables over domain.

Source

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));

Source

pub fn domain(&self) -> &D

Return a reference to the coefficient domain.

Source

pub fn n_vars(&self) -> usize

Return the number of variables.

Source

pub fn n_terms(&self) -> usize

Return the number of non-zero terms.

Source

pub fn is_zero(&self) -> bool

Return whether this is the zero polynomial.

Source

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

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

Source

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.

Source

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

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

Source

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

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

Source

pub fn zero(&self) -> Self

Return the zero polynomial with the same shape.

Source

pub fn one(&self) -> Self

Return the constant polynomial 1 over the same shape.

Source

pub fn neg(&self) -> Self

Return the negation of this polynomial.

Source

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

Add another polynomial.

Panics if the polynomials have different numbers of variables.

Source

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

Subtract another polynomial.

Panics if the polynomials have different numbers of variables.

Source

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

Multiply by a scalar coefficient.

Source

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

Multiply two polynomials.

Panics if the polynomials have different numbers of variables.

Source

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

Return the terms sorted according to the monomial ordering.

Source

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.

Source

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

Return the leading monomial (exponent vector) or None.

Source

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

Return the leading coefficient or None.

Source

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.

Source

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).

Source

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))

Source

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));

Source

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));

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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));

Source §

impl SparseMultivariatePolynomial<IntegerDomain, Lex>

Source

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

Factor this bivariate integer polynomial into irreducible factors with multiplicities.

The current implementation treats the polynomial as univariate in the first variable $x$ with coefficients in $\mathbb{Z}[y]$ and uses Wang’s Hensel-lifting algorithm. It succeeds when the leading coefficient in $x$ is an integer constant.

§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);

Source §

impl SparseMultivariatePolynomial<FiniteField, Lex>

Source

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

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

The current implementation treats the polynomial as univariate in the first variable $x$ with coefficients in $\mathbb{F}_p[y]$ and uses Hensel lifting. It succeeds when the leading coefficient in $x$ is a field constant and the polynomial is square-free (or the derivative in $x$ is non-zero).