Naive polynomial multiplication
graph TD; 1(A, B coeff) 2(A, B point) 3(C = AB coeff) 4(C = AB point) 1 --O(n^2)--- 2 1 --O(n^2)--- 3 2 --O(n)--- 4 4 --O(n^2)--- 3
Polynomial multiplication with FFT
graph TD; 1(A, B coeff) 2(A, B point) 3(C = AB coeff) 4(C = AB point) 1 --O(nlogn)--- 2 1 --O(n^2)--- 3 2 --O(n)--- 4 4 --O(nlogn)--- 3
Evaluation with FFT
Problem input
Problem output
How does FFT work?
Recursive algorithm on arbitrary x-points
What would be the complexity of this algorithm?
How do we address this?
Weak negation property definition
Recursive algorithm on points with a weak negation property
What would be the complexity of this algorithm?
Strong negation property definition
We should probably generalize this
n-th root of unity definition
Principal n-th root of unity definition
Why is it interesting to us? Because
Recursive algorithm on x-points with a strong property
Pseudocode for this algorithm is as follows: