MIT 6.1220 — Lectures 22–23

Solution. (String Matching) Switch to a $\pm 1$ encoding, reverse $p$, and compute $s \ast p$. This is $O(n \log n)$.   $\blacksquare$

Solution. (FFT) It's equivalent to compute $p(x) \cdot q(x)$ for polynomials satisfying $\deg (p) = m$ and $\deg(q) = n$.

The driving principle behind our solution is the following.

Fact. Any degree-$n$ polynomial is uniquely determined by its evaluations on any $n + 1$ distinct values.

A good choice of values to evaluate our polynomials on, it turns out, is the full set of $(2^t)^{\text{th}}$ roots of unity.

Claim (Discrete Fourier Transform). Let $n$ be a power of two, and let $\omega := e^{\frac{2\pi i}{n}}$. For any polynomial $p$ with degree $(n - 1)$ or lower, we can compute $\{p(\omega^{k}) \}_{k = 0}^{n - 1}$ in $O(n \log n)$ time.

Proof: Divide and conquer. Say the runtime is $T(n)$.

• Denote $p_{\text{even}}(x)$ and $p_{\text{odd}}(x)$ so that $p(x) = p_{\text{even}}(x^2) + x \cdot p_{\text{odd}}(x^2)$.

• In $2T\left(\frac{n}{2}\right)$ time, compute $\{p_{\text{even}}(\omega^{2k})\}_{k = 0}^{n / 2 - 1}$ and $\{p_{\text{odd}}(\omega^{2k})\}_{k = 0}^{n / 2 - 1}$.

• In $O(n)$ time, we can then compute:

  $$p(\omega^k) = \begin{cases} p_{\text{even}}\left(\omega^{2k}\right) + \omega^k \cdot p_{\text{odd}}\left(\omega^{2k}\right) & \text{if $k < \frac{n}{2}$.} \\ p_{\text{even}}\left(\omega^{2k - n}\right) - \omega^{k - n/2} \cdot p_{\text{odd}}\left(\omega^{2k - n}\right) & \text{if $k \geq \frac{n}{2}$.} \end{cases}$$

This yields $T(n) = 2T\left(\frac{n}{2}\right) + O(n)$, which solves to $T(n) = O(n \log n)$.   $\square$

Thus, we select $\omega = e^{\frac{2\pi i}{N}}$ for some power-of-two $N > m + n$, then compute $\{p(\omega^k) \cdot q(\omega^k)\}_{k = 0}^{N - 1}$ in $O((m + n) \log (m + n))$ time. It remains to invert the DFT process above to extract $p(x) \cdot q(x)$ from here.

Claim (Inverse Discrete Fourier Transform). Given the values $\{p(\omega^k)\}_{k = 0}^{n - 1}$ for some polynomial $p$ with degree $(n - 1)$ or lower, we can compute $p(x)$ in $O(n \log n)$ time.

Proof: The point is that the Inverse DFT is no harder than the DFT.

Say $p(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n - 1}x^{n - 1}$. Then the DFT computes a matrix product:

$$\begin{bmatrix} p(\omega^0) \\ p(\omega^1) \\ p(\omega^2) \\ \vdots \\ p(\omega^{n - 1}) \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n - 1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n - 1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n - 1} & \omega^{2(n - 1)} & \cdots & \omega^{(n - 1)(n - 1)} \end{bmatrix}}_{W} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n - 1} \end{bmatrix}.$$

We effectively wish to find an efficient way to multiply the LHS by $W^{-1}$. The trick is that $W$ satisfies a really nice property:

$$\left(\overline{W} W\right)_{s, t} = \sum_{k = 0}^{n - 1} \overline{W}_{s, k} \cdot W_{k, t} = \sum_{k = 0}^{n - 1} \overline{\omega^{s \cdot k}} \cdot \omega^{k \cdot t} = \sum_{k = 0}^{n - 1} \omega^{k \cdot (t - s)} = \begin{cases} n & \text{ if } s = t. \\ 0 & \text{ otherwise.} \end{cases}$$

Therefore, $\overline{W}W = nI$, so all we need to do is perform the DFT (with $\overline{\omega}$ in place of $\omega$) on the LHS and divide by $n$.   $\square$

And that completes the implementation of FFT!   $\blacksquare$