The fast Fourier transform Flashcards
what is the degree of the product of two degree-d polynomials?
a polynomial of degree 2d
Naively how much time does it take to multiply two polynomials for degree d?
O(d^2), since for every coefficient of the product polynomial, it takes O(k) steps, and there are 2d+1 coefficients resulting with:
O(1) + O(2) + .. + O(2d) = O(d^2)
How the fact the “A degree-d polynomial is uniquely charactersized by its values at any d+1 distinct points” gives us an alternative representation of polynomials?
for a degree-n polynomial A, how much time does it take to compute A(z) for some z?
How much time does it take to compute C(z), using A(z)*B(z)
Both take O(n).
Describe the process of identifying the coefficents of C(x) = A(x)*B(x)
input: A and B coefficient.
Evaluation of A(z) * B(z) = C(z) for 2d+1 points.
Interpolation back to find the coefficient of C(x)
What is the great buzz behind FFT?
it can evaluate a polynomial of degree d<=n, for n points in O(nlogn) time instead of O(n^2)
What is the first interesting idea as to how to reduce the time complexity for evaluation?
we can choose positive-negative paris, thus having the computations required for A(x) and A(-x) overlap a lot since for even power k, pow(x,k) = pow(-x, k).
Explain why A(x) can be written as:
A’(x^2) + xA’‘(x^2)
where A’ = even coefficients and A’’ = odd coefficients.
Analyze the improvement in run-time
A is of degree-n -> Aeven and Aodd are of degree d/2.
we need to evalutate only n/2 points. x0^2, x1^2…
That is,
first problem: evalute n points on degree n polynomial.
updated problem: evaluate n/2 points on two d/2 degree polynomial. Then finding A(x) demands O(n) arithmetic.
T(n) = 2T(n/2) + O(n) = O(nlogn)
What is the problem with this method of pos/min points?
How can we have complex number which satisfies the recursion requirements. That is, that the next call of the n/2 points are still plus/neg couples?
We reverse-engineer the problem:
we start with 1 and each time find the roots.
since each number has 2 roots in the complex realm, we have:
1 -> -1, 1 -> -i, i, -1, 1 -> …. till we reach n points.
which are the complex nth roots of unity. The solutions for the equation z^n = 1
What is the fast formula for extracting all nth roots of unity?
If n is even, what is special about the nth roots?
They are plus-minus paired!
and when squared, we get the (n/2)nd roots of unity.
Write the fast Fourier transform
Write in matrix form the transformation for coefficient of a polynomial to values, given n values.
What is the property of a Vandermonde matrix?
If x(0), .., x(n-1) are distinct numbers, them M is invertible.
How does the Vandermonde matrix property help us with the FFT algoritm?
When our matrix is represented using the nth roots of unity, which properties it suggests?
Since M is invertible, we can express the coefficient in terms of values!
In brief: evaluation is multiplication by M, while interpolation is multiplication by M^-1
With the roots of unity, the (j,k)th entry is w^(jk)
with the roots of unity, M’s columns are orthogonal to each other, and they form a basis
How does it help us that the effect of multiplying by M is to rotate it from the standart basis to the Fourier basis?
We know that the inverse of M is the opposite rotation, from the Fourier basis back into the standard basis.
thus - M(w)^-1 = 1/nM(w^-1)
Prove the lemma:
and show how it helps to prove the inversion formula
How can the FFT be achieved using matrix multiplication?
Write the function FFT(a, w)
a is an n-size vector represents the coefficients of some polynomial.
n is a power of 2.
w is the nth root of unity.
Write the fast Fourier transform butterfly
write down for n = 8
