Struct SparseMultilinearExtension 

pub struct SparseMultilinearExtension<F: Field> {
    pub evaluations: BTreeMap<usize, F>,
    pub num_vars: usize,
    /* private fields */
}

Stores a multilinear polynomial in sparse evaluation form.

Fields

evaluations: BTreeMap<usize, F>

tuples of index and value

num_vars: usize

number of variables

Implementations

impl<F: Field> SparseMultilinearExtension<F>

pub fn from_evaluations<'a>( num_vars: usize, evaluations: impl IntoIterator<Item = &'a (usize, F)>, ) -> Self

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

Outputs an l-variate multilinear extension where value of evaluations are sampled uniformly at random. The number of nonzero entries is num_nonzero_entries and indices of those nonzero entries are distributed uniformly at random.

Note that this function uses rejection sampling. As number of nonzero entries approach 2 ^ num_vars, sampling will be very slow due to large number of collisions.

pub fn to_dense_multilinear_extension(&self) -> DenseMultilinearExtension<F>

Convert the sparse multilinear polynomial to dense form.

Trait Implementations

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

type Output = SparseMultilinearExtension<F>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = SparseMultilinearExtension<F>

The resulting type after applying the + operator.

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

Performs the + operation.

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

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

Performs the += operation.

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

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

Performs the += operation.

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

fn add_assign(&mut self, other: Self)

Performs the += operation.

impl<F: Field> CanonicalDeserialize for SparseMultilinearExtension<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 SparseMultilinearExtension<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 SparseMultilinearExtension<F>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

fn default() -> SparseMultilinearExtension<F>

Returns the “default value” for a type.

impl<F: Hash + Field> Hash for SparseMultilinearExtension<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 SparseMultilinearExtension<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 Sparse multilinear polynomial, Lookup_evaluation takes log time to the size of polynomial.

type Output = F

The returned type after indexing.

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

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. The number of nonzero entries is sqrt(2^num_vars) and indices of those nonzero entries are distributed uniformly at random.

fn num_vars(&self) -> usize

Returns the number of variables in self

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 fix_variables(&self, partial_point: &[F]) -> Self

Reduce the number of variables of self by fixing the partial_point.len() variables at partial_point.

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 SparseMultilinearExtension<F>

type Output = SparseMultilinearExtension<F>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

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

fn eq(&self, other: &SparseMultilinearExtension<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 SparseMultilinearExtension<F>

type Point = Vec<F>

The type of evaluation points for this polynomial.

fn degree(&self) -> usize

Returns the total degree of the polynomial

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

Evaluates self at the given point in Self::Point.

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

type Output = SparseMultilinearExtension<F>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = SparseMultilinearExtension<F>

The resulting type after applying the - operator.

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

Performs the - operation.

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

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

Performs the -= operation.

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

fn sub_assign(&mut self, other: Self)

Performs the -= operation.

impl<F: Field> Valid for SparseMultilinearExtension<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 SparseMultilinearExtension<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 SparseMultilinearExtension<F>

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