Struct FactoredMultilinear 

pub struct FactoredMultilinear<P: PackedField, Data: BufferData<P> = Vec<P>> { /* private fields */ }

A multilinear that factorizes across disjoint runs of its variables.

Some weights are a product of small pieces rather than one table. An equality indicator over several axes factorizes across them, for instance.

Storing such a weight whole costs the product of the pieces’ lengths. Storing the pieces costs their sum.

    whole:   2^(n_1 + n_2 + n_3) entries
    factors: 2^n_1 + 2^n_2 + 2^n_3 entries

The saving is what lets a sumcheck range over a space far too large to materialize, so long as nothing ever asks for the whole table at once.

Variable order

Factors are held lowest run first.

A factor over n variables owns the next n bits of the index, above the bits the factors before it own. So the last factor owns the highest variables, and is the one a fold consumes first.

    index = [ factor 0 bits | factor 1 bits | ... | last factor bits ]
              lowest                                       highest

Examples

// A weight over an operand axis, a shift axis, and a value axis.
let mut weight = FactoredMultilinear::new(vec![operand, shift, value]);
let at_index = weight.get(index);
weight.fold_highest_var(challenge);

Where the factors’ packed words live.

Defaults to the heap, and the point of the parameter is that it need not be.

A caller proving out of an arena hands over arena-backed factors. This holds them as they are, rather than forcing a copy onto the heap.

Implementations

impl<P: PackedField, Data: BufferData<P>> FactoredMultilinear<P, Data>

pub fn new(factors: impl IntoIterator<Item = FieldBuffer<P, Data>>) -> Self

Builds a multilinear from its factors, lowest variable run first.

A factor with no variables is folded straight into the bound product rather than kept, since it holds a value and no axis.

pub fn n_vars(&self) -> usize

The number of variables still free.

pub fn get(&self, index: usize) -> P::Scalar

The value at one vertex of the hypercube over the free variables.

Each factor reads the bits it owns, and the results multiply. So a lookup costs one multiplication per factor rather than one per variable.

Panics

Panics if the index does not fit the free variables.

pub fn fold_highest_var(&mut self, challenge: P::Scalar)

Fixes the highest free variable to a value.

The highest variable belongs to the last factor, so that is the factor this folds. A factor whose variables are all bound holds one value, which moves into the bound product.

Panics

Panics if no variable is free.

Trait Implementations

impl<P: Clone + PackedField, Data: Clone + BufferData<P>> Clone for FactoredMultilinear<P, Data>

where P::Scalar: Clone,

fn clone(&self) -> FactoredMultilinear<P, Data>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<P: Debug + PackedField, Data: Debug + BufferData<P>> Debug for FactoredMultilinear<P, Data>

where P::Scalar: Debug,

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

Formats the value using the given formatter.