Notes - DAA HT23, Fast Fourier Transform

Created: February 01, 2023

Flashcards

What’s the time complexity of multiplying two $n$-bit integers together with the FFT method?
\[\Omega(n \log n \log \log n)\]

When we write $(a _ 1 a _ 2 a _ 3 \ldots b _ n) _ {10}$ and $(b _ 1 b _ 2 b _ 3 \ldots b _ n) _ {10}$, the numbers are “really”:

\[\begin{aligned} &a_1 \cdot 10^{n-1} + \ldots + a_n \cdot 10^0 \\\\ &b_1 \cdot 10^{n-1} + \ldots + b_n \cdot 10^0 \end{aligned}\]

What key observation lets you use the FFT algorithm to multiply these two numbers?

Treat them like polynomials which will be evaluated at $10$:

\[\begin{aligned} &A(x) = a_1x^{n-1}+ \cdots + a_n \\\\ &B(x) = b_1x^{n-1}+ \cdots + b_n \end{aligned}\]

and then multiply these polynomials together.

What are the two ways of representing a polynomial $A(x)$?
  • Coefficient form, $A(x) = a _ 0 + a _ 1 x + \cdots + a _ {n-1} x^{n-1}$.
  • Point value form, $\left[(p _ 0, A(p _ 0)),\cdots,(p _ {n-1}, A(p _ {n-1}))\right]$

What’s the advantage of using the coefficient form of a polynomial

\[A(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}\]

opposed to the point-value form?

Evalutation can be done in $\Theta(n)$ arithmetic operations with Horner’s rule.

Given a polynomial

\[A(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}\]

How could you evaluate it at $x _ 0$ in $\Theta(n)$ via Horner’s rule?
\[A(x_0) = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-2} + x_0 a_{n-1})\cdots))\]

What’s the advantage of using the point-value form of a polynomial

\[\left[(p_0, A(p_0)),\cdots,(p_{n-1}, A(p_{n-1}))\right]\]

opposed to the coefficient form?

Multiplication can be done in $\Theta(n)$ arithmetic operations.

Given two polynomials represented in point-value form $A$ and $B$, with

\[\begin{aligned} \left[(p_0, A(p_0)),\cdots,(p_{n-1}, A(p_{n-1}))\right] \\\\ \left[(p_0, B(p_0)),\cdots,(p_{n-1}, B(p_{n-1}))\right] \end{aligned}\]

What’s the point-value form for their product?
\[\left[(p_0, A(p_0)B(p_0)),\cdots,(p_{n-1}, A(p_{n-1})B(p_{n-1}))\right]\]

The interpolation problem for polynomials is concerned with converting the point-value form of a polynomial $\left[(x _ 0, y _ 0), \ldots, (x _ {n-1}, y _ {n-1})\right]$ to its coefficient representation $A(x) = a _ 0 + a _ 1 x + \ldots + a _ {n-1} x _ {n-1}$. Solving what matrix equation achieves this?
\[\begin{bmatrix} 1 \& x_0 \& x_0^2 \& \dots \& x_0^{n-1} \\\\ 1 \& x_1 \& x_1^2 \& \dots \& x_1^{n-1} \\\\ \vdots \& \vdots \& \vdots \& \ddots \& \vdots \\\\ 1 \& x_{n-1} \& x_{n-1}^2 \& \dots \& x_{n-1}^{n-1} \\\\ \end{bmatrix} \begin{bmatrix} a_0 \\\\ a_1 \\\\ \vdots \\\\ a_{n-1} \\\\ \end{bmatrix} = \begin{bmatrix} y_0 \\\\ y_1 \\\\ \vdots \\\\ y_{n-1} \\\\ \end{bmatrix}\]

What are matrices (often used in interpolation problems) that look like

\[\begin{bmatrix} 1 \& x_0 \& x_0^2 \& \dots \& x_0^{n-1} \\\\ 1 \& x_1 \& x_1^2 \& \dots \& x_1^{n-1} \\\\ \vdots \& \vdots \& \vdots \& \ddots \& \vdots \\\\ 1 \& x_{n-1} \& x_{n-1}^2 \& \dots \& x_{n-1}^{n-1} \\\\ \end{bmatrix}\]

called?

Vandermonde matrices.

Can you summarise the $\Theta(n\log n)$ algorithm for multiplying two polynomials $A(x)$ and $B(x)$ in coefficient form?
  • Use FFT to convert to point-value form
  • Multiply in point-value form
  • Use inverse FFT to convert back to coefficient form

The $\Theta(n \log n)$ algorithm for multiplying two polynomials goes something like this:

  • Use FFT to convert to point-value form
  • Multiply in point-value form
  • Use inverse FFT to convert back to coefficient form

With any choice of evaluation points, this is actually $\Theta(n^2)$. What is special about the choice of evaluation points?

They are specific complex numbers chosen to exploit symmetry in the evalutation process.

Proofs



Related posts