# The fast Fourier transform Flashcards

1
Q

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

A

a polynomial of degree 2d

2
Q

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

A

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)

3
Q

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?

A
4
Q

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)

A

Both take O(n).

5
Q

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

A

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)

6
Q

What is the great buzz behind FFT?

A

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

7
Q

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

A

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

8
Q

Explain why A(x) can be written as:

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

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

A
9
Q

Analyze the improvement in run-time

A

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)

10
Q

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

A
11
Q

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?

A

We reverse-engineer the problem:

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

12
Q

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

A
13
Q

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

A

They are plus-minus paired!

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

14
Q

Write the fast Fourier transform

A
15
Q

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

A
16
Q

What is the property of a Vandermonde matrix?

A

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

17
Q

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?

A

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

18
Q

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

A

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)

19
Q

Prove the lemma:

and show how it helps to prove the inversion formula

A
20
Q

How can the FFT be achieved using matrix multiplication?

A
21
Q

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.

A
22
Q

Write the fast Fourier transform butterfly

A
23
Q
A

write down for n = 8

24
Q
A