Module hypercube 

Multilinear tensor expansions, generic over the hypercube the coefficients are indexed by.

An n-variate multilinear is stored as 2^n coefficients. The basis those coefficients are taken against factors as a tensor product over the variables. Every variable contributes the same two-element basis (b_0, b_1) of linear polynomials. That single choice fixes the cube, and with it what each coefficient means:

basis (1 - X, X)    vertices {0, 1}      coefficients are evaluations
basis (1, X)        vertices {0, inf}    coefficients are monomial coefficients

The object built over a cube again and again is the equality indicator. Written eq(X, Y), it extends the predicate X == Y multilinearly over the cube. Fixing one operand to a point leaves 2^n coefficients, called the expansion of that point.

Fixing a variable of a multilinear to a value likewise depends on the cube. The two halves the variable splits the coefficients into are weighted by its basis there.

Every routine here is generic over the cube. The Boolean-cube specializations live beside them, in the sibling equality indicator and fold modules.

Structs

InfCube

The infinity cube {0, inf}^n, whose per-variable basis is (1, X).

OneCube

The Boolean cube {0, 1}^n, whose per-variable basis is (1 - X, X).

Traits

Hypercube

A hypercube of coefficients for multilinear polynomials.

Functions

eq_ind

Evaluates the equality indicator multilinear at a pair of points.

eq_ind_partial_eval

Computes the partial evaluation of the equality indicator polynomial.

eq_ind_partial_eval_in

Builds the equality indicator expansion of a point into a buffer drawn from an allocator.

eq_ind_partial_eval_scalars

Computes the partial evaluation of the equality indicator polynomial, returning scalars.

eq_ind_truncate_low_inplace

Truncates a built equality indicator expansion to its low indexed variables.

eq_ind_zero

Evaluates the equality indicator multilinear with one operand fixed to all zeros.

fold_highest_var

Fixes the highest variable of a multilinear to a value, writing into memory from an allocator.

fold_highest_var_inplace

Fixes the highest variable of a multilinear to a value, in place.

scaled_eq_ind_partial_eval

Computes the partial evaluation of the equality indicator polynomial, scaled by a constant.

scaled_eq_ind_partial_eval_into

Builds the scaled equality indicator expansion of a point in a caller-supplied store.

scaled_eq_ind_partial_eval_scalars

Computes the scaled partial evaluation of the equality indicator, returning scalars.

tensor_prod_eq_ind

Tensor of values with the equality indicator evaluated at extra coordinates.