- Representing polynomials as coefficients, roots, or sample values
- Converting from coefficients to samples is a linear transformation
- Divide-and-conquer via collapsible points
- Complex roots of unity are collapsible
- FFT = O(n log n) time conversion from coefficients to values at roots of unity
- FFT is almost its own inverse.
…Read more
Less…
- Tags
-