PDF of Eric’s handwritten notes are here.
Complex Numbers Review
We can represent a complex number as a point in the complex plane or in polar coordinates where:
Euler’s Identity gives a convenient form for a complex number by noting that and thus .
A benefit of the representation in polar coordinates is that they are convenient for multiplication:
A few convenient basic facts:
Multiplication by :
We will use the nth complex roots of unity:
A complex number that is a solution to the equation is referred to as an root of unity. If we work in polar coordinates, then we can obtain a very nice classification of all roots of unity.
We are looking for such that . This implies that and for some . We denote:
and then all of the roots of unity are
- They satisfy the property when is even i.e.
To see why, observe that and
- The squares of the roots of unity are the roots of unity when is a power of . To see why, observe that
Given a polynomial of degree at most , , we want to choose points and evaluate at these points. (We can view as a polynomial of degree in order to get it at points.) We require the points to satisfy the property, i.e., for . Hence we will choose the points to be the roots of unity, i.e., for .
Define the two polynomials based on the even and odd terms of . Let and . We will recursively compute at points . Property (2) above says that these points are the roots of unity. Then we obtain at points by using the relation .
Notice that our original problem was to evaluate a polynomial of degree at the roots of unity. We then have two recursive subproblems, namely evaluating the polynomials and of degree at the roots of unity. Thus we have 2 subproblems which are of the same form and of half the size. We are now ready to present the FFT algorithm.
Later (to do Inverse FFT) we will evaluate a polynomial again at the roots of unity, but in the reverse order . To make the procedure modular enough to fit both situations we take as an input parameter where is any root of unity. Our FFT procedure will follow by setting and we will later see that our inverse FFT procedure will follow by setting .
Input: Coefficients of : and a root of unity
If , Return
Call to get
Call to get
For to :
This can be written more concisely as:
If , Return
For to :
To evaluate at points, we evaluate and at points, and combine them in time. Thus, we have the recurrence which solves to .
Recall from the previous lecture that to multiply and , we evaluate these polynomials at points and multiply to obtain at points. Finally, we need to convert back from point representation to coefficient representation to get the coefficients of . In this section, we will see how to perform this key interpolation step.
For a polynomial , when we apply , we get .
In general, for points , we have:
In particular, for points , we have:
Let , ,
In order to compute the vector from vector , we need an efficient way to compute .
Observe that since as is an root of unity.
Then, to compute , we will apply FFT.
That gives our algorithm for inverse FFT. Given the values of at the roots of unity, view those values as the coefficients for a new polynomial. Then run FFT for this new polynomial with parameter , scale the output by a factor and this gives the coefficients for .
It remains to prove the lemma. We will need the following basic fact.
Claim: For any root of unity , then .
Proof: For any number notice that
Let . Since is a root of unity we have that . Hence:
Thus, either and/or . We assumed that and thus we have that , which proves the claim.
Proof of Key Lemma:
To prove the lemma, we need to show that
where is the identity matrix (this matrix has 1’s on the diagonal and 0 for all other entries).
Let’s first look at the diagonal entries of . Thus, consider entry of for some :
Now, consider entry where of :
Let and note that since and . Then,
This proves the lemma.