The fast Fourier transform

Question 1

what is the degree of the product of two degree-d polynomials?

Answer 1

a polynomial of degree 2d

Question 2

Naively how much time does it take to multiply two polynomials for degree d?

Answer 2

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)

Question 3

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?

Answer 3

Question 4

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)

Answer 4

Both take O(n).

Question 5

Describe the process of identifying the coefficents of C(x) = A(x)*B(x)

Answer 5

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)

Question 6

What is the great buzz behind FFT?

Answer 6

it can evaluate a polynomial of degree d<=n, for n points in O(nlogn) time instead of O(n^2)

Question 7

What is the first interesting idea as to how to reduce the time complexity for evaluation?

Answer 7

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).

Question 8

Explain why A(x) can be written as:

A’(x^2) + xA’‘(x^2)

where A’ = even coefficients and A’’ = odd coefficients.

Answer 8

Question 9

Analyze the improvement in run-time

Answer 9

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)

Question 10

What is the problem with this method of pos/min points?

Answer 10

Question 11

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?

Answer 11

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

Question 12

What is the fast formula for extracting all nth roots of unity?

Answer 12

Question 13

If n is even, what is special about the nth roots?

Answer 13

They are plus-minus paired!

and when squared, we get the (n/2)nd roots of unity.

Question 14

Write the fast Fourier transform

Answer 14

Question 15

Write in matrix form the transformation for coefficient of a polynomial to values, given n values.

Answer 15

Question 16

What is the property of a Vandermonde matrix?

Answer 16

If x(0), .., x(n-1) are distinct numbers, them M is invertible.

Question 17

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?

Answer 17

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

Question 18

How does it help us that the effect of multiplying by M is to rotate it from the standart basis to the Fourier basis?

Answer 18

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)

Question 19

Prove the lemma:

and show how it helps to prove the inversion formula

Answer 19

Question 20

How can the FFT be achieved using matrix multiplication?

Answer 20

Question 21

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.

Answer 21

Question 22

Write the fast Fourier transform butterfly

Answer 22

Question 23

Answer 23

write down for n = 8