ark_poly/evaluations/multivariate/multilinear/
mod.rs

1mod dense;
2mod sparse;
3
4pub use dense::DenseMultilinearExtension;
5pub use sparse::SparseMultilinearExtension;
6
7use ark_std::{
8    fmt::Debug,
9    hash::Hash,
10    ops::{Add, AddAssign, Index, Neg, SubAssign},
11    vec::*,
12};
13
14use ark_ff::{Field, Zero};
15
16use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
17use ark_std::rand::Rng;
18
19use crate::Polynomial;
20
21#[cfg(all(
22    target_has_atomic = "8",
23    target_has_atomic = "16",
24    target_has_atomic = "32",
25    target_has_atomic = "64",
26    target_has_atomic = "ptr"
27))]
28type DefaultHasher = ahash::AHasher;
29
30#[cfg(not(all(
31    target_has_atomic = "8",
32    target_has_atomic = "16",
33    target_has_atomic = "32",
34    target_has_atomic = "64",
35    target_has_atomic = "ptr"
36)))]
37type DefaultHasher = fnv::FnvHasher;
38
39/// This trait describes an interface for the multilinear extension
40/// of an array.
41///
42/// The latter is a multilinear polynomial represented in terms of its
43/// evaluations over the domain {0,1}^`num_vars` (i.e. the Boolean hypercube).
44///
45/// Index represents a point, which is a vector in {0,1}^`num_vars` in little
46/// endian form. For example, `0b1011` represents `P(1,1,0,1)`
47pub trait MultilinearExtension<F: Field>:
48    Sized
49    + Clone
50    + Debug
51    + Hash
52    + PartialEq
53    + Eq
54    + Add
55    + Neg
56    + Zero
57    + CanonicalSerialize
58    + CanonicalDeserialize
59    + for<'a> AddAssign<&'a Self>
60    + for<'a> AddAssign<(F, &'a Self)>
61    + for<'a> SubAssign<&'a Self>
62    + Index<usize>
63    + Polynomial<F, Point = Vec<F>>
64{
65    /// Returns the number of variables in `self`
66    fn num_vars(&self) -> usize;
67
68    /// Outputs an `l`-variate multilinear extension where value of evaluations
69    /// are sampled uniformly at random.
70    fn rand<R: Rng>(num_vars: usize, rng: &mut R) -> Self;
71
72    /// Relabel the point by swapping `k` scalars from positions `a..a+k` to
73    /// positions `b..b+k`, and from position `b..b+k` to position `a..a+k`
74    /// in vector.
75    ///
76    /// This function turns `P(x_1,...,x_a,...,x_{a+k - 1},...,x_b,...,x_{b+k - 1},...,x_n)`
77    /// to `P(x_1,...,x_b,...,x_{b+k - 1},...,x_a,...,x_{a+k - 1},...,x_n)`
78    fn relabel(&self, a: usize, b: usize, k: usize) -> Self;
79
80    /// Reduce the number of variables of `self` by fixing the
81    /// `partial_point.len()` variables at `partial_point`.
82    fn fix_variables(&self, partial_point: &[F]) -> Self;
83
84    /// Returns a list of evaluations over the domain, which is the boolean
85    /// hypercube. The evaluations are in little-endian order.
86    fn to_evaluations(&self) -> Vec<F>;
87}
88
89/// swap the bits of `x` from position `a..a+n` to `b..b+n` and from `b..b+n` to `a..a+n` in little endian order
90pub(crate) const fn swap_bits(x: usize, a: usize, b: usize, n: usize) -> usize {
91    let a_bits = (x >> a) & ((1usize << n) - 1);
92    let b_bits = (x >> b) & ((1usize << n) - 1);
93    let local_xor_mask = a_bits ^ b_bits;
94    let global_xor_mask = (local_xor_mask << a) | (local_xor_mask << b);
95    x ^ global_xor_mask
96}
ark_poly/evaluations/multivariate/multilinear/mod.rs

ark_poly/evaluations/multivariate/multilinear/
mod.rs
