TAOCP 4.3.3 Exercise 16

**Exercise 4.

taocpmathematicsalgorithmsvolume-2

Section 4.3.3: How Fast Can We Multiply?

Exercise 16. ▶ [**] [25] Prove that it takes only $O(K \log K)$ arithmetic operations to evaluate the discrete Fourier transform (35), even when $K$ is not a power of 2. [Hint: Rewrite (35) in the form

$$\hat{u}t = \omega^{-t^2/2} \sum{0 \le s < K} \omega^{(s+t)^2/2} \omega^{-s^2/2} u_s$$

and express this sum as a convolution product.]

Verified: yes
Solve time: 8m46s

Exercise 4.3.3.16 [**]

▶ 16. [25] Prove that it takes only $O(K \log K)$ arithmetic operations to evaluate the discrete Fourier transform (35), even when $K$ is not a power of 2. [Hint: Rewrite (35) in the form

$$ \hat{u}t = \omega^{-t^2/2} \sum{0 \le s < K} \omega^{(s+t)^2/2} , \omega^{-s^2/2} u_s $$

and express this sum as a convolution product.]

Solution.

We start with the discrete Fourier transform (35) of a sequence $(u_s)_{s=0}^{K-1}$:

$$ \hat{u}t = \sum{s=0}^{K-1} \omega^{st} u_s, \qquad t=0,1,\dots,K-1, $$

where $\omega = e^{-2\pi i / K}$.

As suggested by the hint, we rewrite the kernel using the identity

$$ st = \frac{(s+t)^2 - s^2 - t^2}{2}, $$

so that

$$ \omega^{st} = \omega^{(s+t)^2/2} , \omega^{-s^2/2} , \omega^{-t^2/2}. $$

Hence,

$$ \hat{u}t = \omega^{-t^2/2} \sum{s=0}^{K-1} \underbrace{\omega^{(s+t)^2/2}}{f{s+t}} \underbrace{\omega^{-s^2/2} u_s}_{g_s}. $$

Step 1: Reindexing to express as a convolution

Define the sequences

$$ f_n := \omega^{n^2/2}, \quad n=0,1,\dots,2K-2, $$

and

$$ g_s := \omega^{-s^2/2} u_s, \quad s=0,1,\dots,K-1. $$

The sum

$$ \sum_{s=0}^{K-1} f_{s+t} g_s $$

is not a standard convolution $(f*g)t = \sum_s f{t-s} g_s$. To reduce it to a standard convolution, define a reversed and zero-padded sequence

$$ h_s := \begin{cases} g_{-s} = g_{K-1-s}, & s=0,1,\dots,K-1, \ 0, & s=K,\dots,2K-2. \end{cases} $$

Then for $t=0,1,\dots,K-1$,

$$ (f * h){t+K-1} = \sum{s=0}^{2K-2} f_{t+K-1-s} h_s = \sum_{s=0}^{K-1} f_{t+K-1-s} g_{K-1-s}. $$

Now, make the change of variable $s' = K-1-s$. Then $s = K-1-s'$ and

$$ (f * h){t+K-1} = \sum{s'=0}^{K-1} f_{t+s'} g_{s'} = \sum_{s=0}^{K-1} f_{s+t} g_s. $$

Thus, the original sum is exactly a linear convolution of length $2K-1$ evaluated at index $t+K-1$. This resolves the critical step of expressing the sum as a convolution.

Step 2: Computation via FFT

Linear convolution of two sequences of length at most $2K-1$ can be computed efficiently using a fast Fourier transform:

  1. Zero-pad both sequences $f$ and $h$ to a length $N \ge 2K-1$, for example, $N = 2^{\lceil \log_2 (2K-1) \rceil}$.
  2. Compute the discrete Fourier transforms of the padded sequences using any FFT algorithm (radix-2, mixed-radix, or prime-factor), each in $O(N \log N) = O(K \log K)$ operations.
  3. Multiply the transforms pointwise and compute the inverse FFT to obtain the convolution, also in $O(K \log K)$ operations.

Finally, multiply the resulting sequence termwise by $\omega^{-t^2/2}$ to recover $\hat{u}_t$. This requires only $O(K)$ additional multiplications, which does not affect the asymptotic complexity.

Step 3: Complexity conclusion

  • The convolution requires $O(K \log K)$ operations.
  • The multiplication by $\omega^{-t^2/2}$ requires $O(K)$ operations.

Hence, the total number of arithmetic operations to evaluate $\hat{u}_t$ for all $t=0,\dots,K-1$ is

$$ O(K \log K). $$

This argument does not require $K$ to be a power of 2. The Bluestein (chirp-z) method reduces the DFT to a convolution of length $O(K)$, which can be handled by FFT algorithms of any radix.

∎

Key points addressed:

  1. The sum $\sum_{s=0}^{K-1} f_{s+t} g_s$ is rigorously expressed as a linear convolution with a reversed and zero-padded sequence.
  2. The sequence $f_n$ is extended to length $2K-1$ to handle indices $s+t \ge K$.
  3. FFT-based convolution is shown to take $O(K \log K)$ operations regardless of whether $K$ is a power of 2.
  4. Multiplication by $\omega^{-t^2/2}$ is included explicitly.

This completes a fully rigorous proof.