FFT Algorithm
Intro
A polynomial in coefficient form (e.g. \(1+x-x^2+x^5)\) can be converted to point-value 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 point-value form through evaluation in \(O(nlogn)\) using whats known as the FFT algorithm. Multiplication in point-value 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 4-th roots of unity, \(w_4\) to the FFT algorithm. Point-value form = \(FFT(a, w_4)\). Repeat for \(B(x)\).
-
Once we have the results, use element-wise multiplication to obtain the \(c\), the point-value representation of \(C(x)\). To interpolate take the inverse of \(w_4\), \(w_4^-1 = <1,-i,-1,i>\), and \(c=[20, -5-i, -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,-1-i]\)
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, 2-3i]\)
\(c = a * b\), element-wise multiplication results in \([20, -5-i, -2,-5+i]\).
To move from point-value 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\).