Struct DenseMultilinearExtension 

pub struct DenseMultilinearExtension<F: Field> {
    pub evaluations: Vec<F>,
    pub num_vars: usize,
}

Stores a multilinear polynomial in dense evaluation form.

Fields

evaluations: Vec<F>

The evaluation over {0,1}^num_vars

num_vars: usize

Number of variables

Implementations

impl<F: Field> DenseMultilinearExtension<F>

pub fn from_evaluations_slice(num_vars: usize, evaluations: &[F]) -> Self

Construct a new polynomial from a list of evaluations where the index represents a point in {0,1}^num_vars in little endian form. For example, 0b1011 represents P(1,1,0,1)

pub fn from_evaluations_vec(num_vars: usize, evaluations: Vec<F>) -> Self

Construct a new polynomial from a list of evaluations where the index represents a point in {0,1}^num_vars in little endian form. For example, 0b1011 represents P(1,1,0,1).

Example

use ark_test_curves::bls12_381::Fr;
use ark_poly::{MultilinearExtension, Polynomial, DenseMultilinearExtension};

// Construct a 2-variate MLE, which takes value 1 at (x_0, x_1) = (0, 1)
// (i.e. 0b01, or index 2 in little endian)
// f1(x_0, x_1) = x_1*(1-x_0)
let mle = DenseMultilinearExtension::from_evaluations_vec(
    2, vec![0, 0, 1, 0].iter().map(|x| Fr::from(*x as u64)).collect()
);
let eval = mle.evaluate(&vec![Fr::from(-2), Fr::from(17)]); // point = (x_0, x_1)
assert_eq!(eval, Fr::from(51));

pub fn relabel_in_place(&mut self, a: usize, b: usize, k: usize)

Relabel the point in place by switching k scalars from position a to position b, and from position b to position a in vector.

This function turns P(x_1,...,x_a,...,x_{a+k - 1},...,x_b,...,x_{b+k - 1},...,x_n) to P(x_1,...,x_b,...,x_{b+k - 1},...,x_a,...,x_{a+k - 1},...,x_n)

pub fn iter(&self) -> Iter<'_, F>

Returns an iterator that iterates over the evaluations over {0,1}^num_vars

pub fn iter_mut(&mut self) -> IterMut<'_, F>

Returns a mutable iterator that iterates over the evaluations over {0,1}^num_vars

pub fn concat(polys: impl IntoIterator<Item = impl AsRef<Self>> + Clone) -> Self

Concatenate the evaluation tables of multiple polynomials. If the combined table size is not a power of two, pad the table with zeros.

Example

use ark_test_curves::bls12_381::Fr;
use ark_poly::{MultilinearExtension, Polynomial, DenseMultilinearExtension};
use ark_ff::One;

// Construct a 2-variate multilinear polynomial f1
// f1(x_0, x_1) = 2*(1-x_1)*(1-x_0) + 3*(1-x_1)*x_0 + 2*x_1*(1-x_0) + 6*x_1*x_0
let mle_1 = DenseMultilinearExtension::from_evaluations_vec(
    2, vec![2, 3, 2, 6].iter().map(|x| Fr::from(*x as u64)).collect()
);
// Construct another 2-variate MLE f2
// f2(x_0, x_1) = 1*x_1*x_0
let mle_2 = DenseMultilinearExtension::from_evaluations_vec(
  2, vec![0, 0, 0, 1].iter().map(|x| Fr::from(*x as u64)).collect()
);
let mle = DenseMultilinearExtension::concat(&[&mle_1, &mle_2]);
// The resulting polynomial is 3-variate:
// f3(x_0, x_1, x_2) = (1 - x_2)*f1(x_0, x_1) + x_2*f2(x_0, x_1)
// Evaluate it at a random point (1, 17, 3)
let point = vec![Fr::one(), Fr::from(17), Fr::from(3)];
let eval_1 = mle_1.evaluate(&point[..2].to_vec());
let eval_2 = mle_2.evaluate(&point[..2].to_vec());
let eval_combined = mle.evaluate(&point);

assert_eq!(eval_combined, (Fr::one() - point[2]) * eval_1 + point[2] * eval_2);

Trait Implementations

impl<'a, F: Field> Add<&'a DenseMultilinearExtension<F>> for &DenseMultilinearExtension<F>

type Output = DenseMultilinearExtension<F>

The resulting type after applying the + operator.

fn add(self, rhs: &'a DenseMultilinearExtension<F>) -> Self::Output

Performs the + operation.

impl<F: Field> Add for DenseMultilinearExtension<F>

type Output = DenseMultilinearExtension<F>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<'a, F: Field> AddAssign<&'a DenseMultilinearExtension<F>> for DenseMultilinearExtension<F>

fn add_assign(&mut self, other: &'a Self)

Performs the += operation.

impl<'a, F: Field> AddAssign<(F, &'a DenseMultilinearExtension<F>)> for DenseMultilinearExtension<F>

fn add_assign(&mut self, (f, other): (F, &'a Self))

Performs the += operation.

impl<F: Field> AddAssign for DenseMultilinearExtension<F>

fn add_assign(&mut self, other: Self)

Performs the += operation.

impl<F: Field> AsRef<DenseMultilinearExtension<F>> for DenseMultilinearExtension<F>

fn as_ref(&self) -> &Self

Converts this type into a shared reference of the (usually inferred) input type.

impl<F: Field> CanonicalDeserialize for DenseMultilinearExtension<F>

fn deserialize_with_mode<R: Read>( reader: R, compress: Compress, validate: Validate, ) -> Result<Self, SerializationError>

The general deserialize method that takes in customization flags.

fn deserialize_compressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the compressed form if applicable. Performs validation if applicable.

fn deserialize_compressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the compressed form if applicable, without validating the deserialized value.

fn deserialize_uncompressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the uncompressed form. Performs validation if applicable.

fn deserialize_uncompressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the uncompressed form, without validating the deserialized value.

impl<F: Field> CanonicalSerialize for DenseMultilinearExtension<F>

fn serialize_with_mode<W: Write>( &self, writer: W, compress: Compress, ) -> Result<(), SerializationError>

The general serialize method that takes in customization flags.

fn serialized_size(&self, compress: Compress) -> usize

Returns the size in bytes of the serialized version of self with the given compression mode.

fn serialize_compressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

Serializes self into writer using the compressed form if applicable.

fn compressed_size(&self) -> usize

Returns the size in bytes of the compressed serialized version of self.

fn serialize_uncompressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

Serializes self into writer using the uncompressed form.

fn uncompressed_size(&self) -> usize

Returns the size in bytes of the uncompressed serialized version of self.

impl<F: Clone + Field> Clone for DenseMultilinearExtension<F>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Field> Debug for DenseMultilinearExtension<F>

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

Formats the value using the given formatter.

impl<F: Default + Field> Default for DenseMultilinearExtension<F>

fn default() -> DenseMultilinearExtension<F>

Returns the “default value” for a type.

impl<F: Hash + Field> Hash for DenseMultilinearExtension<F>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<F: Field> Index<usize> for DenseMultilinearExtension<F>

fn index(&self, index: usize) -> &Self::Output

Returns the evaluation of the polynomial at a point represented by index.

Index represents a vector in {0,1}^num_vars in little endian form. For example, 0b1011 represents P(1,1,0,1)

For dense multilinear polynomial, index takes constant time.

type Output = F

The returned type after indexing.

impl<'a, F: Field> IntoIterator for &'a DenseMultilinearExtension<F>

type IntoIter = Iter<'a, F>

Which kind of iterator are we turning this into?

type Item = &'a F

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, F: Field> IntoIterator for &'a mut DenseMultilinearExtension<F>

type IntoIter = IterMut<'a, F>

Which kind of iterator are we turning this into?

type Item = &'a mut F

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, F: Field> Mul<&'a F> for &DenseMultilinearExtension<F>

type Output = DenseMultilinearExtension<F>

The resulting type after applying the * operator.

fn mul(self, scalar: &'a F) -> Self::Output

Performs the * operation.

impl<F: Field> Mul<F> for DenseMultilinearExtension<F>

type Output = DenseMultilinearExtension<F>

The resulting type after applying the * operator.

fn mul(self, scalar: F) -> Self::Output

Performs the * operation.

impl<'a, F: Field> MulAssign<&'a F> for DenseMultilinearExtension<F>

fn mul_assign(&mut self, scalar: &'a F)

Performs the *= operation.

impl<F: Field> MulAssign<F> for DenseMultilinearExtension<F>

fn mul_assign(&mut self, scalar: F)

Performs the *= operation.

impl<F: Field> MultilinearExtension<F> for DenseMultilinearExtension<F>

fn fix_variables(&self, partial_point: &[F]) -> Self

Return the MLE resulting from binding the first variables of self to the values in partial_point (from left to right).

Note: this method can be used in combination with relabel or relabel_in_place to bind variables at arbitrary positions.

use ark_test_curves::bls12_381::Fr;

// Constructing the two-variate multilinear polynomial x_0 + 2 * x_1 + 3 * x_0 * x_1
// by specifying its evaluations at [00, 10, 01, 11]
let mle = DenseMultilinearExtension::from_evaluations_vec(
    2, vec![0, 1, 2, 6].iter().map(|x| Fr::from(*x as u64)).collect()
);

// Bind the first variable of the MLE, x_0, to the value 5, resulting in
// a new polynomial in one variable: 5 + 17 * x
let bound = mle.fix_variables(&[Fr::from(5)]);

assert_eq!(bound.to_evaluations(), vec![Fr::from(5), Fr::from(22)]);

}

fn num_vars(&self) -> usize

Returns the number of variables in self

fn rand<R: Rng>(num_vars: usize, rng: &mut R) -> Self

Outputs an l-variate multilinear extension where value of evaluations are sampled uniformly at random.

fn relabel(&self, a: usize, b: usize, k: usize) -> Self

Relabel the point by swapping k scalars from positions a..a+k to positions b..b+k, and from position b..b+k to position a..a+k in vector.

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

Returns a list of evaluations over the domain, which is the boolean hypercube. The evaluations are in little-endian order.

impl<F: Field> Neg for DenseMultilinearExtension<F>

type Output = DenseMultilinearExtension<F>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<F: PartialEq + Field> PartialEq for DenseMultilinearExtension<F>

fn eq(&self, other: &DenseMultilinearExtension<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: Field> Polynomial<F> for DenseMultilinearExtension<F>

fn evaluate(&self, point: &Self::Point) -> F

Evaluate the dense MLE at the given point

Example

use ark_test_curves::bls12_381::Fr;

// The two-variate polynomial p = x_0 + 3 * x_0 * x_1 + 2 evaluates to [2, 3, 2, 6]
// in the two-dimensional hypercube with points [00, 10, 01, 11]:
// p(x_0, x_1) = 2*(1-x_1)*(1-x_0) + 3*(1-x_1)*x_0 + 2*x_1*(1-x_0) + 6*x_1*x_0
let mle = DenseMultilinearExtension::from_evaluations_vec(
    2, vec![2, 3, 2, 6].iter().map(|x| Fr::from(*x as u64)).collect()
);

// By the uniqueness of MLEs, `mle` is precisely the above polynomial, which
// takes the value 54 at the point (x_0, x_1) = (1, 17)
let eval = mle.evaluate(&[Fr::one(), Fr::from(17)].into());
assert_eq!(eval, Fr::from(54));

type Point = Vec<F>

The type of evaluation points for this polynomial.

fn degree(&self) -> usize

Returns the total degree of the polynomial

impl<'a, F: Field> Sub<&'a DenseMultilinearExtension<F>> for &DenseMultilinearExtension<F>

type Output = DenseMultilinearExtension<F>

The resulting type after applying the - operator.

fn sub(self, rhs: &'a DenseMultilinearExtension<F>) -> Self::Output

Performs the - operation.

impl<F: Field> Sub for DenseMultilinearExtension<F>

type Output = DenseMultilinearExtension<F>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<'a, F: Field> SubAssign<&'a DenseMultilinearExtension<F>> for DenseMultilinearExtension<F>

fn sub_assign(&mut self, other: &'a Self)

Performs the -= operation.

impl<F: Field> SubAssign for DenseMultilinearExtension<F>

fn sub_assign(&mut self, other: Self)

Performs the -= operation.

impl<F: Field> Valid for DenseMultilinearExtension<F>

const TRIVIAL_CHECK: bool

Whether the check method is trivial (i.e. always returns Ok(())). If this is true, the batch_check method will skip all checks and return Ok(()). This should be set to true for types where check is trivial, e.g. integers, field elements, etc. This is false by default. This is primarily an optimization to skip unnecessary checks in batch_check.

fn check(&self) -> Result<(), SerializationError>

Checks whether self is valid. If self is valid, returns Ok(()). Otherwise, returns an error describing the failure. This method is called by deserialize_with_mode if validate is Validate::Yes.

fn batch_check<'a>( batch: impl Iterator<Item = &'a Self> + Send, ) -> Result<(), SerializationError>

where Self: 'a,

Checks whether all items in batch are valid. If all items are valid, returns Ok(()). Otherwise, returns an error describing the first failure.

impl<F: Field> Zero for DenseMultilinearExtension<F>

fn zero() -> Self

Returns the additive identity element of Self, 0.

fn is_zero(&self) -> bool

Returns true if self is equal to the additive identity.

fn set_zero(&mut self)

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

impl<F: Eq + Field> Eq for DenseMultilinearExtension<F>

impl<F: Field> StructuralPartialEq for DenseMultilinearExtension<F>