Computation of power polynomial is O(d * 2^d) instead of O(2^d) #864

lucasxia01 · 2024-02-21T18:25:27Z

We compute the power polynomial with an outer loop that iterates over 2^d (d being the log size and also the number of betas), and use a O(d) inner loop that multiplies the appropriate betas together. We can optimize this to O(2^d) method that is also easily parallelizable by computing a binary tree.

Started in this commit.

Adds the pow poly bench. This PR was supposed to also optimize the pow poly computation, but I measured that it takes around 45ms of the whole 6-iter client IVC benchmark, so its not worth doing for now. Links a couple of optimization issues to the codebase: AztecProtocol/barretenberg#857 and AztecProtocol/barretenberg#864.

Adds the pow poly bench. This PR was supposed to also optimize the pow poly computation, but I measured that it takes around 45ms of the whole 6-iter client IVC benchmark, so its not worth doing for now. Links a couple of optimization issues to the codebase: #857 and #864.

lucasxia01 added the optimization label Feb 21, 2024

lucasxia01 mentioned this issue Feb 23, 2024

chore: add pow poly bench and link optimization issues AztecProtocol/aztec-packages#4725

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Computation of power polynomial is O(d * 2^d) instead of O(2^d) #864

Computation of power polynomial is O(d * 2^d) instead of O(2^d) #864

lucasxia01 commented Feb 21, 2024 •

edited

Loading

Computation of power polynomial is O(d * 2^d) instead of O(2^d) #864

Computation of power polynomial is O(d * 2^d) instead of O(2^d) #864

Comments

lucasxia01 commented Feb 21, 2024 • edited Loading

lucasxia01 commented Feb 21, 2024 •

edited

Loading