Caching polynomial tree for prover's faster FFT computation?

[jasonge27]

Pinocchio's paper mentioned an optimization technique

"Hence we implemented an FFT-based O(nlogn) polynomial multiplication library and used a polynomial interpolation algorithm [48] that builds a binary tree of polynomials, giving total time O(nlog^2n)." and the prover can "also save the polynomial tree used to accelerate the computation" for repeated tasks

With a fixed circuit, if the prover needs to process repeated computation with different inputs. Do you see this could lead to major performance boost?

[jasonge27]

Looking at the function

template<typename FieldT>
void _basic_serial_radix2_FFT(std::vector<FieldT> &a, const FieldT &omega)

in the file libfqfft/evaluation_domain/domains/basic_radix2_domain_aux.tcc, it seems that we have a lot of exponentiation of the unit root in the following two lines const FieldT w_m = omega^(n/(2*m)); w *= w_m;

If we move this exponentiation to pre-processing, is it likely to achieve 2-3 times speed up from here?

[madars]

The Pinocchio system operates in a setting where the finite field does not have 2^k-th roots of unity, whereas for our algebraic setup we can use more efficient radix-2 FFTs. A latter Geppetto system uses http://www.csd.uwo.ca/~eschost/publications/BostanSchost.pdf to speed up this computation even in absence of 2^k-th roots of unity (this is also implemented in our libfqfft library).

With regards to the second question, this exponentiation is only done O(log n) times, so is unlikely to give a big speed-up for the O(n log n)-sized computation. But if a clean patch gives substantial improvement, we'd welcome it :)