Struct ark_poly::evaluations::multivariate::multilinear::SparseMultilinearExtension

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

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

type Output = SparseMultilinearExtension<F>

The resulting type after applying the + operator.

fn add(self, other: SparseMultilinearExtension<F>) -> Self

Performs the + operation.

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

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

Performs the += operation.

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

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

Performs the += operation.

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

fn add_assign(&mut self, other: Self)

Performs the += operation.

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

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

Reads Self from reader.

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

Reads Self from reader without compression.

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

Reads self from reader without compression, and without performing validity checks. Should be used only when the input is trusted.

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

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

Serializes self into writer. It is left up to a particular type for how it strikes the serialization efficiency vs compression tradeoff. For standard types (e.g. bool, lengths, etc.) typically an uncompressed form is used, whereas for algebraic types compressed forms are used.

fn serialized_size(&self) -> usize

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

Serializes self into writer without compression.

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

Serializes self into writer without compression, and without performing validity checks. Should be used only when there is no danger of adversarial manipulation of the output.

fn uncompressed_size(&self) -> usize

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

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

Returns a copy of the value.

pub 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: Eq + Field> Eq for SparseMultilinearExtension<F>

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

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

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

type Output = F

The returned type after indexing.

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.

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

fn num_vars(&self) -> usize

Returns the number of variables in self

fn evaluate(&self, point: &[F]) -> Option<F>

Evaluates self at the given the vector point in slice. If the number of variables does not match, return None.

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 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.

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

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

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

fn ne(&self, other: &SparseMultilinearExtension<F>) -> bool

This method tests for !=.

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

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

impl<'a, 'b, F: Field> Sub<&'a SparseMultilinearExtension<F>> for &'b 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<SparseMultilinearExtension<F>> for SparseMultilinearExtension<F>

type Output = SparseMultilinearExtension<F>

The resulting type after applying the - operator.

fn sub(self, other: SparseMultilinearExtension<F>) -> Self

Performs the - operation.

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

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

Performs the -= operation.

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

fn sub_assign(&mut self, other: Self)

Performs the -= operation.

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.

pub fn set_zero(&mut self)

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