A compilation of concepts I want to remember...

» Home
» 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$$.