L11-12 (Fast Fourier Transform)

Question 1

Suppose we have 2 polynomials A(x) and B(x) which both have a degree of d. We multiply them to get C(x) using the naive method. What is the time complexity for this?

Answer 1

It would take O(d^2) time to multiply two polynomials of degree d the naive (brute force) way

Question 2

What are some applications of the Fast-Fourier Transform (FFT)?

Answer 2

• Polynomial Multiplication
• Signal Processing
• Data compression
• Image processing

Question 3

A polynomial
a0 + a1x + a2x^2 + …

Can be characterized in two representations. What are they?

Answer 3

1. Coefficient representation (the most common) in which we have its coefficients for each degree term
2. Value representation in which we have a set of the values of the polynomial, we would need exactly d+1 such points to represent a polynomial of degree d.

Question 4

We want to do polynomial multiplication on polynomials A(x) and B(x) of degree d, to get C(x), using the following 4 step process:

1. Selection
2. Evaluation
3. Multiplication
4. Interpolation

Briefly explain these 4 steps

Answer 4

1. Selection is where we pick n >= 2d+1 unique numbers x_0, x_1, …, x_n-1 (the nth roots of unity)
2. Evaluation is where we compute the value representations of A and B from these unique numbers A(x_0), A(x_1), …, B(x_0), B(x_1), …
3. Multiplication is where we compute the value representations from these unique numbers for C as C(x_i) = A(x_i)*B(x_i) for all x numbers
4. Interpolation is where we recover the coefficients for C from its values representation obtained in the previous step

Question 5

One of the steps in matrix multiplication is the selection step in which we chose n >= 2d+1 numbers to plug into our polynomials.

How does FFT (fast fourier transform) allow us to select these n numbers?

note that these n numbers are called the “nth roots of unity”

Answer 5

Firstly, we define:
w = e^(2pi * i / n)

(i is sqrt(-1))

Then, we select the values of x as follows:
x_j = w^j

for j = 0, 1, … , n-1

This completes the selection step where we get the n th roots of unity (values) which are used in the following steps.

Question 6

In the polynomial multiplication of A(x)*B(x), at the selection phase, we use FFT to select n values (x_0, x_1, … ) using the x_j = w^j method.

These values are called the “nth roots of unity”.

How does this method of selection help in the evaluation step?

Answer 6

Firstly, we split A(x) into its odd and even powers, and rewrite it as:

A(x) = A_e(x^2) + x*A_o(x^2)

These odd and even sub-polynomials are evaluated at x^2. Their degrees are less than n/2 - 1

Whenever we evaluate the nth roots of unity, the x^2 will cancel out the complex numbers and allows us to use divide and conquer approach to evaluate at the n/2 th roots of unity.

Question 7

Suppose we have the “nth roots of unity” using the x_j = w^j, where w = e^(2pi*i/n)

What happens to these values if we square each of these values in the nth roots of unity - that is, turn:
{x_0, x_1, x_2, …}
into
{x_0^2, x_1^2, x_2^2, …}

Answer 7

Squaring the nth roots of unity gives us two copies of the (n/2)th roots of unity.

For example if we have the 8th roots of unity, we’ll get two copies of the 4th roots of unity

Squaring a complex number is like scaling its angle on the Re/Im axis by two. This is the property of “nth roots of unity” which makes it desirable

Question 8

In the polynomial multiplication of A(x)*B(x), at the evaluation phase, explain how we can use divide and conquer to evaluate the value of A(x) for all the nth roots of unity

n >= 2d+1, d is the degree of A. Remember that the nth roots of unity are extracted using x_j = w^j

w = e^(2pii / n)

Answer 8

To evaluate A(x) at the nth roots of unity:
{x_0, x_1, … x_n-1}

We evaluate two polynomials of half the size A_e(x^2) and A_o(x^2) at the n/2 th roots of unity.

Once we evaluate these, we can recombine them (in divide and conquer fashion) to get A(x) at the n th roots of unity:

A(x) = A_e(x^2) + x*A_o(x^2)

With this, the evaluation phase is complete

note that A_e() is the even degree coeffs and A_o() is the odd degree coeffs

Question 9

Write out Pseudocode for the evaluation phase of polynomial multiplication using FFT.

Suppose the input is the coefficients of a polynomial, A (a0, a1, …) , and w (a complex number).

And the output is value representation of A: [A(w^0), A(w^1), … ]

note that w = e^(2pii / n)

Where n is a power of 2 and is greater than 2d+1 where d is the degree of the polynomial A

Answer 9

function FTT(A, w):
- base case, if w == 1: return A(1)
- express A(x) in the form A_e(x^2) + x*A_o(x^2)
- call FFT(Ae, w^2)
- call FFT(Ao, w^2)
- for j = 0 to n-1, compute A(w^j) = Ae(w^2j) + w^j * Ao(w^2j)
- return A(w^0), A(w^1), …

note that FFT(Ao, w^2) or FFT(Ae, w^2) will Ao or Ae at the n/2 th roots of unity

Question 10

Using the FFT algorithm to compute the value representation of a polynomial of degree d < n-1,

• What is the constraint on what n should be? Why?
• What is the runtime of this algorithm?

Answer 10

• n needs to be a power of 2 so that when we recursively compute w^2j, we will eventually arrive at 1
• The runtime is O(n log n) using the following recurrence relation:

T(n) = 2T(n/2) + O(n)

Question 11

For the interpolation step in polynomial multiplication,

How does the values representation of a polynomial relate to its coefficients through matrix multiplications? Where does inverting a matrix come into play?

Answer 11

• The values representation vector is equal to the matrix multiplication of
  the “values matrix” ( Mn(w) ) with the coefficients vector
• Therefore, in the interpolation step, we get the polynomial’s coefficients by inverting the matrix Mn(w)

Note that the “values matrix” is a the matrix of the polynomial’s coefficients when plugging in each of the nth roots of unity into the polynomial (they are in terms of w)

Question 12

What is the matrix inversion formula for Mn(w)?

Note that Mn(w) would be an n x n matrix in terms of w

Answer 12

Mn(w) ^ -1 = 1/n * Mn(w^-1)

To invert the matrix, multiply by 1/n and evaluate at w^-1

Question 13

For the interpolation step in polynomial multiplication,

How would FFT be used to compute the coefficients from the value representation of a polynomial and w?

note that w = e^(2pii / n), and n is a power of 2 greater than 2d+1

Answer 13

(a0, a1, … ) = (1/n)*FFT( (A(w^0), A(w^1), … ) , w^-1)

We get the coefficients by calling FFT with the value representation and w^-1 as inputs, and then multiplying that by 1/n.

This works because [coeffs vector] = inverse of Mn(w) * [values repr vector], and inverse of Mn(w) is equal to 1/n * Mn(w^-1)

Question 14

Two polynomials of degree d can be multiplied in _____ time by using FTT for the _______ and _______ steps

Answer 14

• O(d log d)
• evaluation
• interpolation

Question 15

Whats the fastest way to multiply two n-bit binary numbers? and how fast is this?

Answer 15

Representing the binary numbers in polynomials, and then using polynomial multiplication. It is O(n log n) time