This repository was archived by the owner on Jun 4, 2025. It is now read-only.
Optimize compute quotient polys #198
Description
Description:
Computes the quotient polynomials (sum alpha^i C_i(x)) / Z_H(x) for alpha in alphas,
where the C_is are the Stark constraints. The current implementation is at compute_quotient_polys.
Solution: inspired by Plonky3.
A quick rundown of the optimizations in this function:
We are trying to compute sum_i alpha^i * (p(X) - y)/(X - z),
for each z an opening point, y = p(z). Each p(X) is given as evaluations in bit-reversed order
in the columns of the matrices. y is computed by barycentric interpolation.
X and p(X) are in the base field; alpha, y and z are in the extension.
The primary goal is to minimize extension multiplications.
- Instead of computing all alpha^i, we just compute alpha^i for i up to the largest width
of a matrix, then multiply by an "alpha offset" when accumulating.
a^0 x0 + a^1 x1 + a^2 x2 + a^3 x3 + ...
= a^0 ( a^0 x0 + a^1 x1 ) + a^2 ( a^0 x2 + a^1 x3 ) + ...
(see `alpha_pows`, `alpha_pow_offset`, `num_reduced`)
- For each unique point z, we precompute 1/(X-z) for the largest subgroup opened at this point.
Since we compute it in bit-reversed order, smaller subgroups can simply truncate the vector.
(see `inv_denoms`)
- Then, for each matrix (with columns p_i) and opening point z, we want:
for each row (corresponding to subgroup element X):
reduced[X] += alpha_offset * sum_i [ alpha^i * inv_denom[X] * (p_i[X] - y[i]) ]
We can factor out inv_denom, and expand what's left:
reduced[X] += alpha_offset * inv_denom[X] * sum_i [ alpha^i * p_i[X] - alpha^i * y[i] ]
And separate the sum:
reduced[X] += alpha_offset * inv_denom[X] * [ sum_i [ alpha^i * p_i[X] ] - sum_i [ alpha^i * y[i] ] ]
And now the last sum doesn't depend on X, so we can precompute that for the matrix, too.
So the hot loop (that depends on both X and i) is just:
sum_i [ alpha^i * p_i[X] ]
with alpha^i an extension, p_i[X] a base