Reduce the next perturbator calculation cost in exchange for memory

[codygunton]

Zac pointed out this optimization a while ago and I forgot to write it down until now.

After the the first IVC step, the perturbator is $F(X) = \sum pow_i(\beta + X\delta) f_i(\omega)$ where $\omega$ is the accumulator $\omega = \omega^* = L_0(\gamma)\omega_{old} + L_1(\gamma)\omega_1$ computed in the previous round. Naively computing this without structuring involves executing the relations $n = \text{circuit size}$-many times. Zac's observation is that we are close to having the needed values $f_i(\omega)$ in the previous IVC step. Namely, the combiner $G(X) = \sum pow(\beta^*)f_i(L_0(X)\omega_{old} + L_1(X)\omega_1)$ is a sum of $n$ small-degree (say 12 for concreteness) univariate polynomials. If we store these $12n$ field elements from the previous round, we can replace the computation of $f_i(\omega)$ via a relation execution (potentially many field operations since our relations are complicated) by a single degree-12 polynomial evaluation (~12 mul-adds via barycentric evaluation).

As with any optimization, we should see where this sits in the hierarchy of potential optimizations before implementing. This is especially the case in light of the structuring of the execution trace, which significantly reduces the amount of work spent on execution relations (but note the exception of the permutation relation!).