Struct mvpoly::monomials::Sparse

pub struct Sparse<F: PrimeField, const N: usize, const D: usize> {
    pub monomials: HashMap<[usize; N], F>,
}

Represents a multivariate polynomial in N variables with coefficients in F. The polynomial is represented as a sparse polynomial, where each monomial is represented by a vector of N exponents.

Fields

monomials: HashMap<[usize; N], F>

Trait Implementations

impl<const N: usize, const D: usize, F: PrimeField> Add<&Sparse<F, N, D>> for &Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the + operator.

fn add(self, other: &Sparse<F, N, D>) -> Self::Output

Performs the + operation.

impl<const N: usize, const D: usize, F: PrimeField> Add<&Sparse<F, N, D>> for Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the + operator.

fn add(self, other: &Sparse<F, N, D>) -> Self::Output

Performs the + operation.

impl<const N: usize, const D: usize, F: PrimeField> Add<Sparse<F, N, D>> for &Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the + operator.

fn add(self, other: Sparse<F, N, D>) -> Self::Output

Performs the + operation.

impl<const N: usize, const D: usize, F: PrimeField> Add<Sparse<F, N, D>> for Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<F: Clone + PrimeField, const N: usize, const D: usize> Clone for Sparse<F, N, D>

fn clone(&self) -> Sparse<F, N, D>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const N: usize, const D: usize, F: PrimeField> Debug for Sparse<F, N, D>

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

Formats the value using the given formatter.

impl<const N: usize, const D: usize, F: PrimeField> From<Dense<F, N, D>> for Sparse<F, N, D>

fn from(dense: Dense<F, N, D>) -> Self

Converts to this type from the input type.

impl<F: PrimeField, const N: usize, const D: usize> From<F> for Sparse<F, N, D>

fn from(value: F) -> Self

Converts to this type from the input type.

impl<F: PrimeField, const N: usize, const D: usize, const M: usize> From<Sparse<F, N, D>> for Result<Sparse<F, M, D>, String>

fn from(poly: Sparse<F, N, D>) -> Result<Sparse<F, M, D>, String>

Converts to this type from the input type.

impl<const N: usize, const D: usize, F: PrimeField> MVPoly<F, N, D> for Sparse<F, N, D>

unsafe fn degree(&self) -> usize

Returns the degree of the polynomial.

The degree of the polynomial is the maximum degree of the monomials that have a non-zero coefficient.

Safety

The zero polynomial as a degree equals to 0, as the degree of the constant polynomials. We do use the unsafe keyword to warn the user for this specific case.

fn eval(&self, x: &[F; N]) -> F

Evaluate the polynomial at the vector point x.

This is a dummy implementation. A cache can be used for the monomials to speed up the computation.

unsafe fn random<RNG: RngCore>(rng: &mut RNG, max_degree: Option<usize>) -> Self

Generate a random polynomial of maximum degree max_degree.

If None is provided as the maximum degree, the polynomial will be generated with a maximum degree of D.

Safety

Marked as unsafe to warn the user to use it with caution and to not necessarily rely on it for security/randomness in cryptographic protocols. The user is responsible for providing its own secure polynomial random generator, if needed.

For now, the function is only used for testing.

fn is_constant(&self) -> bool

fn double(&self) -> Self

fn mul_by_scalar(&self, scalar: F) -> Self

fn from_variable<Column: Into<usize>>( var: Variable<Column>, offset_next_row: Option<usize> ) -> Self

Build the univariate polynomial x_i from the variable i. The conversion into the type usize is unspecified by this trait. It is left to the trait implementation. For instance, in the case of crate::prime, the output must be a prime number, starting at 2. crate::utils::PrimeNumberGenerator can be used. For crate::monomials, the output must be the index of the variable, starting from 0.

fn is_homogeneous(&self) -> bool

Returns true if the polynomial is homogeneous (of degree D). As a reminder, a polynomial is homogeneous if all its monomials have the same degree.

fn homogeneous_eval(&self, x: &[F; N], u: F) -> F

Evaluate the polynomial at the vector point x and the extra variable u using its homogeneous form of degree D.

fn add_monomial(&mut self, exponents: [usize; N], coeff: F)

Add the monomial coeff * x_1^{e_1} * ... * x_N^{e_N} to the polynomial, where e_i are the values given by the array exponents.

fn compute_cross_terms( &self, eval1: &[F; N], eval2: &[F; N], u1: F, u2: F ) -> HashMap<usize, F>

Compute the cross-terms as described in Behind Nova: cross-terms computation for high degree gates

fn modify_monomial(&mut self, exponents: [usize; N], coeff: F)

Modify the monomial in the polynomial to the new value coeff.

fn is_multilinear(&self) -> bool

Return true if the multi-variate polynomial is multilinear, i.e. if each variable in each monomial is of maximum degree 1.

fn from_constant<ChallengeTerm: Clone>( op: Operations<ConstantExprInner<F, ChallengeTerm>> ) -> Self

fn from_expr<Column: Into<usize>, ChallengeTerm: Clone>( expr: Expr<ConstantExpr<F, ChallengeTerm>, Column>, offset_next_row: Option<usize> ) -> Self

Build a value from an expression. This method aims to be used to be retro-compatible with what we call “the expression framework”. In the near future, the “expression framework” should be moved also into this library.

impl<const N: usize, const D: usize, F: PrimeField> Mul<Sparse<F, N, D>> for Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<const N: usize, const D: usize, F: PrimeField> Neg for &Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<const N: usize, const D: usize, F: PrimeField> Neg for Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<const N: usize, const D: usize, F: PrimeField> One for Sparse<F, N, D>

fn one() -> Self

Returns the multiplicative identity element of Self, 1.

fn set_one(&mut self)

Sets self to the multiplicative identity element of Self, 1.

fn is_one(&self) -> boolwhere Self: PartialEq<Self>,

Returns true if self is equal to the multiplicative identity.

impl<const N: usize, const D: usize, F: PrimeField> PartialEq<Sparse<F, N, D>> for Sparse<F, N, D>

Equality is defined as equality of the monomials.

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<const N: usize, const D: usize, F: PrimeField> Sub<&Sparse<F, N, D>> for &Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the - operator.

fn sub(self, other: &Sparse<F, N, D>) -> Self::Output

Performs the - operation.

impl<const N: usize, const D: usize, F: PrimeField> Sub<&Sparse<F, N, D>> for Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the - operator.

fn sub(self, other: &Sparse<F, N, D>) -> Self::Output

Performs the - operation.

impl<const N: usize, const D: usize, F: PrimeField> Sub<Sparse<F, N, D>> for &Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the - operator.

fn sub(self, other: Sparse<F, N, D>) -> Self::Output

Performs the - operation.

impl<const N: usize, const D: usize, F: PrimeField> Sub<Sparse<F, N, D>> for Sparse<F, N, D>

type Output = Sparse<F, N, D>

The resulting type after applying the - operator.

fn sub(self, other: Sparse<F, N, D>) -> Self::Output

Performs the - operation.

impl<const N: usize, const D: usize, F: PrimeField> Zero for Sparse<F, N, D>

fn is_zero(&self) -> bool

Returns true if self is equal to the additive identity.

fn zero() -> Self

Returns the additive identity element of Self, 0.

fn set_zero(&mut self)

Sets self to the additive identity element of Self, 0.

impl<const N: usize, const D: usize, F: PrimeField> Eq for Sparse<F, N, D>