DAA HT23, Fast Fourier Transform
Flashcards
What’s the time complexity of multiplying two $n$-bit integers together with the FFT method?
When we write $(a _ 1 a _ 2 a _ 3 \ldots a _ 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?
Evaluation 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?
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?
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?
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 evaluation process.