Struct ark_poly::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, '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, F: Field> AddAssign<&'a SparseMultilinearExtension<F>> for SparseMultilinearExtension<F>

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

Performs the += operation.

impl<'a, 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_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 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

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

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

Returns a copy of the value.

const 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,

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

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

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

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, 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> Valid for SparseMultilinearExtension<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 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> StructuralEq for SparseMultilinearExtension<F>

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