You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
This repository was archived by the owner on Jun 4, 2025. It is now read-only.
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.
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
Description:
Computes the quotient polynomials
(sum alpha^i C_i(x)) / Z_H(x)foralphainalphas,where the
C_is are the Stark constraints. The current implementation is at compute_quotient_polys.Solution: inspired by Plonky3.