Struct DenseMultilinearPolynomial

pub struct DenseMultilinearPolynomial<F: IsField>
where
    <F as IsField>::BaseType: Send + Sync,
{ /* private fields */ }

Represents a multilinear polynomial as a vector of evaluations (FieldElements) in Lagrange basis.

Implementations

impl<F: IsField> DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

pub fn new(evals: Vec<FieldElement<F>>) -> Self

Constructs a new multilinear polynomial from a collection of evaluations. Pads non-power-of-2 evaluations with zeros.

pub fn num_vars(&self) -> usize

Returns the number of variables.

pub fn evals(&self) -> &Vec<FieldElement<F>>

Returns a reference to the evaluations vector.

pub fn len(&self) -> usize

Returns the total number of evaluations (2^num_vars).

pub fn evaluate( &self, r: Vec<FieldElement<F>>, ) -> Result<FieldElement<F>, MultilinearError>

Evaluates self at the point r (a vector of FieldElements) in O(n) time. r must have a value for each variable.

pub fn evaluate_with( evals: &[FieldElement<F>], r: &[FieldElement<F>], ) -> Result<FieldElement<F>, MultilinearError>

Evaluates a slice of evaluations with the given point r.

pub fn fix_last_variable( &self, r: &FieldElement<F>, ) -> DenseMultilinearPolynomial<F>

Fixes the last variable to the given value r and returns a new DenseMultilinearPolynomial with one fewer variable. Evaluations are ordered so that the first half corresponds to the last variable = 0, and the second half corresponds to the last variable = 1.

Combines each pair of evaluations as: new_eval = a + r * (b - a) This reduces the polynomial by one variable, allowing it to later be collapsed into a univariate polynomial by summing over the remaining variables.

Example (2 variables): evaluations ordered as: [f(0,0), f(0,1), f(1,0), f(1,1)] Fixing the second variable y = r produces evaluations of a 1-variable polynomial: [f(0,r), f(1,r)] computed explicitly as: f(0,r) = f(0,0) + r*(f(0,1)-f(0,0)), f(1,r) = f(1,0) + r*(f(1,1)-f(1,0))

pub fn to_evaluations(&self) -> Vec<FieldElement<F>>

Returns the evaluations of the polynomial on the Boolean hypercube ({0,1}^n). Since we are in Lagrange basis, this is just the elements stored in self.evals.

pub fn to_univariate(&self) -> Polynomial<FieldElement<F>>

Collapses the last variable by fixing it to 0 and 1, sums the evaluations, and returns a univariate polynomial (as a Polynomial) of the form: sum0 + (sum1 - sum0) * x.

pub fn scalar_mul(&self, scalar: &FieldElement<F>) -> Self

Multiplies the polynomial by a scalar.

pub fn extend(&mut self, other: &DenseMultilinearPolynomial<F>)

Extends this DenseMultilinearPolynomial by concatenating another polynomial of the same length.

pub fn merge( polys: &[DenseMultilinearPolynomial<F>], ) -> DenseMultilinearPolynomial<F>

Merges a series of DenseMultilinearPolynomials into one polynomial. Zero-pads the final merged polynomial to the next power-of-two length if necessary.

pub fn from_u64(evals: &[u64]) -> Self

Constructs a DenseMultilinearPolynomial from a slice of u64 values.

Trait Implementations

impl<F: IsField> Add for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

Adds two DenseMultilinearPolynomials. Assumes that both polynomials have the same number of variables.

type Output = Result<DenseMultilinearPolynomial<F>, &'static str>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<F: Clone + IsField> Clone for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

fn clone(&self) -> DenseMultilinearPolynomial<F>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug + IsField> Debug for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

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

Formats the value using the given formatter.

impl<F: IsField> From<(usize, Vec<FieldElement<F>>)> for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

fn from((num_vars, evaluations): (usize, Vec<FieldElement<F>>)) -> Self

Converts to this type from the input type.

impl<F: IsField> Index<usize> for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

type Output = FieldElement<F>

The returned type after indexing.

fn index(&self, index: usize) -> &FieldElement<F>

Performs the indexing (container[index]) operation.

impl<F: IsField> Mul<&FieldElement<F>> for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

type Output = DenseMultilinearPolynomial<F>

The resulting type after applying the * operator.

fn mul(self, rhs: &FieldElement<F>) -> Self::Output

Performs the * operation.

impl<F: IsField> Mul<FieldElement<F>> for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

type Output = DenseMultilinearPolynomial<F>

The resulting type after applying the * operator.

fn mul(self, rhs: FieldElement<F>) -> Self::Output

Performs the * operation.

impl<F: PartialEq + IsField> PartialEq for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,

fn eq(&self, other: &DenseMultilinearPolynomial<F>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl<F: IsField> StructuralPartialEq for DenseMultilinearPolynomial<F>

where <F as IsField>::BaseType: Send + Sync,