A compilation of concepts I want to remember...

Navigation
 » Home
 » About Me
 » Github

Before I forget #1: FFT algorithm

13 May 2019 » fft

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\]

  1. 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)\).

  2. 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>\)

  3. 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)\).

  4. 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\).