Skip to main content

fold_1b_rows_for_b128_split

Function fold_1b_rows_for_b128_split 

Source
pub fn fold_1b_rows_for_b128_split<P, Data>(
    mat: &FieldBuffer<P, Data>,
    eq_lo: &FieldBuffer<B128>,
    eq_hi: &FieldBuffer<B128>,
) -> FieldBuffer<B128>
where P: PackedField<Scalar = B128>, Data: Deref<Target = [P]>,
Expand description

Folds the 1-bit rows of a matrix against an equality tensor supplied as two factors.

§Overview

The equality tensor over n_lo + n_hi coordinates factors along any coordinate split:

    tensor[hi << n_lo | lo] = eq_lo[lo] * eq_hi[hi]

Multiplication distributes over the sum, so the fold regroups exactly:

    sum_x tensor[x] * row[x]
      = sum_hi eq_hi[hi] * ( sum_lo eq_lo[lo] * row[hi, lo] )

Each block of the matrix folds against the low factor alone. Its result is then scaled once by that block’s high-factor entry and merged. Field addition and multiplication are exact. So the result is bit-identical to folding against the materialized tensor.

§Why the factored form is faster

Both effects follow from the tables covering only the low factor, so being built once.

Memory traffic:

  • The full tensor is never written or read, so only the matrix streams through.
  • Folding against a materialized tensor reads one tensor entry per row alongside it.
  • That doubles the stream for the same arithmetic.

Lookup count:

  • A table built once costs nothing per row, so it can cover eight rows instead of four.
  • Eight-row groups halve the lookups and accumulator updates.
  • Those updates are what the fold is bound on, not arithmetic or bandwidth.
  • A table rebuilt per group cannot widen: 256 entries per group costs more than it saves.

The price is one multiply per row, to scale each block by its high-factor entry.

§Preconditions

  • The matrix must have as many rows as the two factors have entries together.
  • A block must cover a whole number of packed elements, so the chunking below aligns. The exception is a matrix that fits inside one packed element, which is a single block.
  • The low factor must span at most one row fold chunk, which is 128 rows.