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, 'b, F: Field> Add<&'a DenseMultilinearExtension<F>> for &'b 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: DenseMultilinearExtension<F>) -> Self

Performs the + operation.

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

fn add_assign(&mut self, other: &'a DenseMultilinearExtension<F>)

Performs the += operation.

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

fn add_assign(&mut self, (f, other): (F, &'a DenseMultilinearExtension<F>))

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) -> &DenseMultilinearExtension<F>

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,

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

where R: Read,

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

where R: Read,

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

where R: Read,

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

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

where W: Write,

fn compressed_size(&self) -> usize

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

where W: Write,

fn uncompressed_size(&self) -> usize

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

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

Returns a copy 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, 'b, F: Field> Mul<&'a F> for &'b 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, 'b, F: Field> Sub<&'a DenseMultilinearExtension<F>> for &'b 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: DenseMultilinearExtension<F>) -> Self

Performs the - operation.

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

fn sub_assign(&mut self, other: &'a DenseMultilinearExtension<F>)

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>

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

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

where Self: 'a,

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>