FFT Algorithm
Intro
A polynomial in coefficient form (e.g. \(1+xx^2+x^5)\) can be converted to pointvalue form in \(O(nlogn)\) time.
Given two polynomials in coefficient form we can convert from coefficient representation which would require \(O(n^2)\) time to pointvalue form through evaluation in \(O(nlogn)\) using whats known as the FFT algorithm. Multiplication in pointvalue form requires \(O(n)\) time. Once the multiplication has been complete we can interpolate to retrieve the coefficient representation of the polynomial.
A concrete example is as follows.
Let: \[A(x) = 1 + x + 2x^2\] \[B(x) = 2 + 3x\]

Find the degree of each \(A(x)\) and \(B(x)\). Let \(n=4\) which is equal to the minimum power of 2 that is greater than the \(deg(A)\) and the \(deg(B)\).

Use the \(n\)th roots of unity. In this case we need the \(4\)th roots of unity which are \(w_4 = <1,i,1,i>\)

Pass the coefficients of the polynomials of \(A(x)\), \(a=[1,1,2,0]\) and the 4th roots of unity, \(w_4\) to the FFT algorithm. Pointvalue form = \(FFT(a, w_4)\). Repeat for \(B(x)\).

Once we have the results, use elementwise multiplication to obtain the \(c\), the pointvalue representation of \(C(x)\). To interpolate take the inverse of \(w_4\), \(w_4^1 = <1,i,1,i>\), and \(c=[20, 5i, 2, 5+i]\) and pass to \(1/n *FFT(c, w_4^1)\) to obtain the coefficients the \([2,5,7,6]\) which maps to the polynomial \(2+5x+7x^2+6x^3\).
FFT: a Divide & Conquer (D&C) approach
A recursive algorithm:
def FFT(a, w):
if w = 1:
return a
a_even = even_indices_of_a
a_odd = odd_indices_of_a
S = FFT(a_even, w^2)
O = FFT(a_odd, w^2)
for i in 0 to n/2:
r_i = S_i + w_i * O_i
r_i+n/2 = S_i  w_i * O_i
return [r_0...r_n]
A concrete example using the polynomials A(x) and B(x) introduced previously. Sorry for the formatting but it will make sense if you stare at it long enough.
LEVEL 1
FFT(\(a=[1,1,2,0]\), \(w_4=[1,i,1,i]\)):
\(w_4\) \(\neq\) \(1\) so continue.
a_even \(= [1,2]\)
a_odd \(= [1,0]\)
\(S\) = \(\color{blue}{FFTEVEN}\)(a_even\(=[1,2]\), \(w_4^2=w_2=[1,1]\)) \(= [3,1]\)
\(O\) = \(\color{purple}{FFTODD}\)(a_odd\(=[1,0], w_4^2=w_2=[1,1]\)) \(= [1, 1]\)
return \([4, 1+i, 2,1i]\)
LEVEL 2
\(\color{blue}{FFTEVEN}\)(a_even\(=[1,2], w_4^2=w_2=[1,1]\))
\(w_2\) \(\neq\) \(1\) so continue.
a_even \(= [1]\)
a_odd \(= [2]\)
\(S\) = \(\color{teal}{FFTEVENEVEN}\)(\(a_even=[1]\), \(w_2^2=w_1=[1]\)) \(= 1\)
\(O\) = \(\color{fuchsia}{FFTEVENODD}\)(\(a_odd=[2]\), \(w_2^2=w_1=[1]\)) \(= 2\)
return \([1+12=3, 1+ 12=1]\)
\(\color{purple}{FFTODD}\)(a_odd\(=[1,0]\), \(w_4^2=w_2=[1,1]\))
\(w_2\) \(\neq\) \(1\) so continue.
a_even \(= [1]\)
a_odd \(= [0]\)
\(S\) = \(\color{red}{FFTODDEVEN}\)(\(a_even=[1], w_2^2=w_1=[1]\)) \(= 1\)
\(O\) = \(\color{green}{FFTODDODD}\)(\(a_odd=[0], w_2^2=w_1=[1]\)) \(= 0\)
return \([1+10=1, 1+ 10=1]\)
LEVEL 3
\(\color{teal}{FFTEVENEVEN}\)(a_even=\([1]\), \(w_2^2=w_1=[1]\))
\(w_1\) \(= 1\) return \(1\)
\(\color{fuchsia}{FFTEVENODD}\)(a_odd=\([2]\), \(w_2^2=w_1=[1]\))
\(w_1\) \(= 1\) return \(2\)
\(\color{red}{FFTODDEVEN}\)(a_even\(=[1]\), \(w_2^2=w_1=[1]\))
\(w_1\) \(= 1\) return \(1\)
\(\color{green}{FFTODDODD}\)(a_odd\(=[0]\), \(w_2^2=w_1=[1]\))
\(w_1\) \(= 1\) return \(0\)
Repeating for b, the results of FFT(\(b, w_4\)) \(= [5, 2+3i, 1, 23i]\)
\(c = a * b\), elementwise multiplication results in \([20, 5i, 2,5+i]\).
To move from pointvalue representation back to coefficients, we can interpolate by using the same FFT D&C algorithm by passing \(c\), and \(w_4^1\) as inputs resulting in the coefficents \([2,5,7,6]\) and a final solution \(2+5x+7x^2 + 6x^3\).