Fast Fourier Transform

Consider the problem of multiplying two polynomials…

$C(x)=A\cdot B=c_0+c_{1}x+\cdots +c_{2d}{x}^{2d}$. The coefficients can be found as: $c_k=a_0{b}_k+a_1{b}_{k-1}+\cdots +a_k{b}_0={\sum }_{i=0}^k{a}_i{b}_{k-i}$.

• For $i>d$, we have $a_i=b_i=0$.
• We need to compute $2d+1$ coefficients.
• Each requires $O(d)$ time to compute using the above expression. Assuming the coefficients are small, each multiplication is $O(1)$.
• Naive polynomial multiplication is $O(d^2)$.

A fast algorithm for polynomial multiplication gives us a fast algorithm for scalar multiplication.

Improvements

A polynomial can be characterized in 2-ways.

1. With coefficients
2. Its value $A(x_n)$ at $n+1$ distinct points (basically plug in a value to x and get the value for the value representation)

For two polynomials of degree d. We want to do three main things.

1. Evaluation: Compute the value representations of A and B
2. Multiplication: Compute the value representation of C
3. Interpolation: Recover the coefficients of C from its value representation

Like I said earlier, the value representation is just arbitrarily choosing values of x and subbing them in and evaluating the polynomial. For interpolation, we just our value representations to make a matrix with an unknown coefficient vector and then solve for that vector by inverting $M$.

The missing steps here are how we choose our $x$’s and how we actually do the evaluation and interpolation. This is what FFT is for.

Actual FFT

Given a complex number $\omega =e^{2\pi i/n}$ Then, consider the following selection for these $x$’s.

• $x_j={\omega }^j$ for each $j=0,\dots ,n-1$.

These points are called the $nth$ roots of unity and are the complex solutions to $z^n=1$.

To help us with evaluation, we want to split the polynomial $A$ into its odd and even powers so that we end up with something like $A(x)=A_e(x^2)+x{A}_o(x^2)$ where each split $A$ can be written as a power of $x^2$. Since we have a split polynomial, we can use a Divide and Conquer approach to evaluation.

Here, we evaluate the two split polynomials at $({\omega }^0{)}^2,\dots ,({\omega }^{n-1}{)}^2$. But if $n$ is a power of 2, then $({\omega }_n^j{)}^2={\omega }_{\frac{n}{2}}^j$, so each ${\omega }^{2j}$ is an $\frac{n}{2}th$ root of unit.

The algorithm is then as follows:

function FFT(A, w)
Input: Coefficients a_0,...,a_d of polynomial A(x) where d <= n-1 and n is a power of two
Output: Value representation A(w^0),...,A(w^n-1)

if w=1:
	return A(1)
express A(x) in the form A_e(x^2)+xA_o(x^2)
call FFT(A_e,w^2) to evaluate A_e at (n/2)th roots of unity
call FFT(A_o,w^2) to evaluate A_o at (n/2)th roots of unity
for j=0 to n-1:
	compute A(w^j)=A_e(w^2j)+w^jA_o(w^2j)
return A(w^0),...,A(w^n-1)

Examining the recurrence relation, $T(n)=2T\left(\frac{n}{2}\right)+O(n)$.

For interpolation, we just need to invert $M$ using the inversion formula…
$M_n(\omega {)}^{-}1=\frac{1}{n}{M}_n({\omega }^{-}1)$.

So we just call $\frac{1}{n}FFT((A({\omega }^0),\dots ,A({\omega }^{n-1})),{\omega }^{-1})$ which gives us the coefficients using the inverted matrix.

Two polynomials of degree d can be multiplied in $O(d\log d)$ time using FFT for evaluation and interpolation. We can use polynomial multiplication to multiply two n-but binary numbers in $O(n\log n)$ time as well.