a bit of fft: a short note on FFT

Mostly for my future references, and will be expanded later.

Fast Fourier Transform

For: Faster polynomial multiplication in $O(N\lg{N})$ time using a divide and conquer strategy, which makes us of a technique called polynomial interpolation, and a fact about the root of unity.

1. Polynomial Interpolation: 
A polynomial $P(x)$ of degree $n$ can be represented by choosing $n$ distinct point on the curve $P(x)$. In other words, $P(x)$ can be constructed back solely by using $n$ points $(x_0,y_0),(x_1,y_1),\ldots,(x_{n-1},y_{n-1})$ where $y_k = P(x_k)$.
Proof that $P(x)$ constructed will be unique: Examine the Vandermonde matrix and its especially cool determinant to derive at the proof.

2. Root of unity
Given $x^n = 1$, there is a complex number $w$ the root of unity such that $w = e^{\frac{2\pi k}{n}}$ for $k = 0,1,2,3,\ldots,n-1$. Then further we have the Cancellation Lemma: $w_{in}^{ik} = w_{n}^{k}$ (direct substitution proof). In particular we have the Halving Lemma: $(w_{n}^{2k+\frac{n}{2}})^2 = (w_{n}^{2k})^2$ (Proof also by direct substitution and making use of the previous relationship).

3. FFT
A polynomial can be partitioned based on even-odd parity of its coefficient index:
$P(x) = a_0+a_1x+a_2x^2+\ldots + a_{n-1}x^{n-1}$
$P(x) = A(x^2) + xB(x^2)$
where
$A(x) = a_0+a_2x+a_4x^2+\ldots$ (even indexed coefficients)
$B(x) = a_1+a_3x+a_5x^2+\ldots$ (odd indexed coefficients)
Therefore we end up with a recursive relationship: to interpolate P(x), we can recursively interpolate A(x) and B(x) and combine its result in $O(N)$ thanks to the Cancellation Lemma and the Halving Lemma which gives rise to a convenient relationship between P and the results from A and B.

4. Pseudo-code:
rec_FFT( polynomial P ): (return interpolated P)
    set n = deg(P)
    if n == 1:
        return P
    set w_k = 1
    set w = $e^{\frac{2\pi}{n}}$ (first root of unity)
    set A = polynomial from even coefficient of P
    set B = polynomial from odd coefficient of P
    a[] = rec_FFT( A )
    b[] = rec_FFT( B )
    for i = 0 to floor(n/2):
        p[i] = a[i] + w_k * b[i]
        p[i + n/2] = a[i] - w_k * b[i]
        w_k = w * w_k
    return p