DC4: FFT Part 1

Question 1

What divide and conquer algorithm do we use for polynomial multiplication?

Answer 1

Fast Fourier Transform (FFT)

Question 1

If we multiply polynomials A(x) and B(x), both degree n-1, what degree is the resulting polynomial C(x)

Answer 1

A(x) = a_0 + a_1x^1 + … + a_(n-1)x^(n-1)
B(x) = b_0 + b_1x^1 + … + b_(n-1)b^(n-1)
C(x) = A(x) B(x), i.e.,

C(x) = c_0 + c_1x^1 + … + c_(2n-2)x^(2n-2)

So, the degree of C(x) is 2n-2

Question 2

How do we compute coefficient c_k from the coefficients of A(x) and B(x)?

Answer 2

c_k = a_0b_k + a_1b_(k-1) + … + a_k * b_0

(Like the dot product of a[0:k] and b[k:0])

Question 3

What is the convolution of coefficient vectors a and b?

Answer 3

c = a * b = the coefficients of C(x), where C(x) = A(x) B(x)

Question 4

What is the time complexity of FFT? What about the naive algorithm for computing the convolution of A(x) and B(x)?

Answer 4

FFT is O(n log n), but the naive is O(n^2)

Question 5

What are the two natural representations of polynomial A(x)?

Answer 5

1) coefficients a = [a_0, …, a_(n-1)]
2) values = A(x_1), …, A(x_(n))

Question 6

How many values are needed to uniquely determine a polynomial of degree n-1?

Answer 6

n

Question 7

What does FFT actually do to a polynomial?

Answer 7

FFT converts the coefficient representation of a polynomial to its value representation and vice versa.

Question 8

Why do we care about the value representation of a polynomial?

Answer 8

While coefficients are a more natural representation, values are more convenient for multiplying polynomials.

Question 9

So how will we use FFT to accomplish polynomial multiplication? (not the algorithm, but the big picture)

Answer 9

1) Use FFT to convert coefficients to values
2) Use values to perform polynomial multiplication
3) Then use FFT to convert back to coefficients

Question 10

How does polynomial multiplication work with the values representation? i.e., why is it so easy?

Answer 10

Given polynomials A(x) and B(x), both of degree n-1, their product C(x) is of degree 2n-2. To compute C(x), we evaluation A(x) and B(x) at 2n points:

A(x_1), …, A(x_2n)
B(x_1), …, B(x_2n)

Then compute C(x) at each of those points:

C(x_i) = A(x_i) B(x_i)

This gives us 2n points, two more than we need to uniquely determine C(x).

Question 11

What is the time complexity of polynomial multiplication using values?

Answer 11

Each multiplication at a point x_i is O(1), so the total time complexity is O(n) since we do this for 2n points.

Question 12

What is the plus-minus property?

Answer 12

For some set of points x_1, …, x_2n,

x_(n+1) = - x_1
x_(n+1) = - x_2
etc.

This way, the squares of opposite points like x_1 and x_(n+1) are equal. This lets us compute half the values during the “divide” step of FFT while still getting the 2n points we need to determine the polynomial C(x).

Question 13

What is the value of the plus-minus property for FFT?

Answer 13

FFT is a D&C algorithm. The division step is where we calculate A(x) = A_even(x^2) + x*A_odd(x^2).

Without the plus-minus property, A_even() and A_odd() have degree n/2 - 1, so the degree decreased by a factor of two, but we would still need to evaluate them at n points.

The plus-minus property is what lets us cut the number of points at which we need to evaluate our subproblems, and therefore truly reduce our subproblems to half the input size.

Question 14

Why does A(x) = A_even(x^2) + x*A_odd(x^2)?

Answer 14

A_even(y) = a_0 + a_2 * y + … + a_(n-2) * y^((n-2)/2)

Note that if we let y = x^2, then each coefficient matches the correct exponent(a_2 gets x^2 for example). We can do this while still keeping the degree of A_even() down to (n-2)/2, which is necessary for halving the subproblem for D&C.

A_odd() works the same way, but only if we divide it by x, i.e. pull x out and put it in front algebraically. Then a_1 gets x^0 instead of x^1 for example.

Question 15

How do we choose 2n points that satisfy the plus-minus property at ALL levels of recursion?

Answer 15

Let’s look at one of our 2n data points. For an input that satisfies the plus-minus property, x_(n+1) = - x_1.

At the second level of recursion, though, we need y_1 = x_1^2, etc., and therefore we need y_(n+1)^2 = - y_1^2. But their both squares! x^2 >= 0 for all real numbers!

This why we need to use complex numbers. This allows y_(n+1)^2 = - y_1^2 to be true.

Question 16

What are the two coordinate systems we can use to represent a complex number z = a + bi?

Answer 16

Cartesian: z = (a, b)
Polar: z = (r, theta) where r is the magnitude off vector z and theta is the angle from x-axis.

Question 17

Why do we like to use polar coordinates in FFT?

Answer 17

Polar coordinates just happen to be convenient for multiplication

Question 18

How do we convert between Cartesian and polar coordinates?

Answer 18

(a, b) = (r* cos theta, r * sin theta)

Question 19

What is Euler’s formula, i.e, the third way to represent a complex number?

Answer 19

x = r(cos theta + i * sin theta) = r * e ^ (i * theta)

Question 20

How do you multiply complex numbers using their polar coordinates?

Answer 20

z_1 * z_2 = (r_1, theta_1) * (r_2, theta_2) = (r_1*r_2, theta_1 + theta_2

Question 21

How do you take the negative of a complex number using polar coordinates?

Answer 21

-1 = (1, pi) in polar coordinates. So if z = (r, theta), then

-z = (r, theta) * (1, pi) = (r, theta + pi)

Think of this in terms of the unit circle. theta + pi is the angle on the opposite side of the circle, so theta + 180 degrees.

Question 22

What values do we choose as our input to FFT?

Answer 22

The nth roots of unity! i.e., the solutions to z^n = 1.

1) They satisfy the plus-minus property
2) (nth roots of unity)^2 = n/2nd roots of unity

Question 23

What is the sum of the nth roots of unity?

Answer 23

0.

By the geometric series equality:
w^0 + w^1 + … + w^(n-1) = (w^n - 1)/(w - 1)

w^n wraps us all the way around the unit circle back to 1, so w^n = 1 and the result is 0.

Question 24

What is the product of the nth roots of unity, even or odd n?

Answer 24

Note that 1 + 2 + … + n-1 = (n-1)n/2

Hence 1ww^2…w^(n-1) = w^{(n-1)n/2}

w^{(n-1)n/2} is