Divide & Conquer: FFT

3 operation we want to sovle fast (for all x)

1. Evaluation == given A(x) and x0 compute A(x0) , naive = O(n^2),  with Horner's Rule = O(n)

Horner's Rue == A(x) = a0 +x(a1 +x(a2 + ... x(an)..)) == doing x product one at a time for evey step == O(n)

2. Addition == given A(x) ,B(x) compute C(x) = A(x) + B(x) , takes O(n) ==    ck = ak+bk (n)times

3. Multiplication == given A(x) B(x) compute C(x)=A(x)*B(x) we can represent Ck as

every k element we need to sum k times == O(n^2) // if j is plus it is convolution 

 

Representation of polynomials

1. Coefficent vector with a monomial basis (above, coefficent vector)

2. Roots and a scale term // A(x) = (x-r0) * (x-r1) .... (x-rn-1) *c

1 ->2  impossible to do becuase there are no ways to solve if degree is larger than 5

addition is difficult even though you convert into 1 there is no guaranteed relation between original 2 and summed value of 1 , multiplication is just concatenating vectors

3. Sample // (x0,y0) , (x1,y1) , .. (xn-1, yn-1) with A(xi) = yi for all i and  each xi is distinct. polynomial interpolation takes O(n^2)

no representation is perfect // we focus on tansforming into Coefficents to Samples and vice versa in nlogn time

Vandermonde matrix

evalutation , represented in matrix notation ,  Coefficent to Samples (V*A) O(n^2) // Sampels to Coefficent (V * \A) getting \A (Guassian elemination) O(n^3) 

 

Divide and Conquer Algorithm (compute V * A , x in SET(X))

1. Divide the polynomial A into its even and odd coefficents 

2. Recursively conquer Aeven(y) for y int SET(X^2) and Aodd(y) for y in SET(X^2) , where X^2 is set of {x^2|x in SET(X)} == 

3. Combine terms. A(x) = Aeven(x^2) + x * Aodd(x^2) for x in SET(X) == linear time O(n)

even though we divide into 2 subproblem but in each subproblelm we still need to evaulate |X| times which is n.

|X| need to be smaller something like |X|/2 , Collapsing Set == |X^2| =|X| , OR |X|=1

|X| =1 ; X = {1} 

|X| = 2 ; X = {-1, 1}

|X| = 4 ; X = {-1,1,-i,i}

as long as n is power of 2 this above set(uniformally spaced in unit circle) is Collpasing Set

DFT = V* A for xk is element of set in above formula where n is  factor of 2

FFT = use DFT + divide and conquer  = nlogn time complexity

 

we now know how to go vector to samples in nlogn but we need vice versa

V(inverse) = V(conjugate)/n   // since complex number's conjugate is just putting minus before complex part we can get it easily

A* = FFT(A) = V x A

B* = FFT(B) = V x B

C* = A* x B* 

C = IFFT(C*)  samples to vector

everything in nlogn 

Reference ==

3. Divide & Conquer: FFT - YouTube