Circle FFT

This section introduces the Circle FFT algorithm, used to interpolate bivariate polynomials over the circle domain using a divide-and-conquer approach.

This section is organized as follows:

• Algorithm: Overview of the Circle FFT algorithm with concrete examples showing the three-step interpolation process.
• Twiddles: Precomputation and storage of twiddle values required for efficient FFT operations.
• Interpolate: Detailed implementation walkthrough of the interpolation function with code breakdown.
• Basis and Dimension Gap: FFT basis for Circle FFT and analysis of the dimension gap in circle polynomial spaces.