TAOCP 4.6.4 Exercise 14
Let $N=2^n,\qquad \omega=e^{2\pi i/N},$ and consider the discrete Fourier transform \qquad 0\le s<N.
Section 4.6.4: Evaluation of Polynomials
Exercise 14. ▶ [HM28] (Fast Fourier transforms.) Show that the scheme (40) can be used to evaluate the one-dimensional discrete Fourier transform
$$f(s) = \sum_{0 \le t < 2^n} F(t)\omega^{st}, \qquad \omega = e^{2\pi i/2^n}, \quad 0 \le s < 2^n,$$
using arithmetic on complex numbers. Estimate the number of arithmetic operations performed.
Verified: yes
Solve time: 1m35s
Setup
Let
$N=2^n,\qquad \omega=e^{2\pi i/N},$
and consider the discrete Fourier transform
$$ \qquad 0\le s<N. $$
Exercise 13 establishes the inverse transform. Exercise 14 asks us to show that the divide-and-conquer scheme (40) yields a fast method for evaluating all values of $f(s)$, and to estimate the number of arithmetic operations.
The essential fact behind scheme (40) is the decomposition of a polynomial into its even and odd parts. If
$$$$
then
$$ \eqno(40) $$
where
$$ \qquad P_1(y)=\sum_{0\le t<N/2}F(2t+1)y^t. $$
Since
$$$$
the transform values are evaluations of $P(x)$ at all $N$th roots of unity.
Solution
Apply (40) with $x=\omega^s$:
$$ f(s) = P_0(\omega^{2s}) + \omega^sP_1(\omega^{2s}). $$
Because
$$ \omega^2=e^{2\pi i/2^{,n-1}}, $$
the numbers
$$ \omega^{2s}, \qquad 0\le s<N, $$
run twice through the complete set of $N/2$ roots of unity of order $2^{n-1}$.
Define
$$ g(r)=\sum_{0\le t<N/2}F(2t),(\omega^2)^{rt}, $$
$$ h(r)=\sum_{0\le t<N/2}F(2t+1),(\omega^2)^{rt}, \qquad 0\le r<N/2. $$
Then $g(r)$ and $h(r)$ are discrete Fourier transforms of length $N/2$. For $0\le r<N/2$,
$$ f(r)=g(r)+\omega^r h(r), $$
and
$$ f(r+N/2) = g(r)+\omega^{r+N/2}h(r). $$
Since
$$ \omega^{N/2}=e^{\pi i}=-1, $$
this becomes
$$ f(r+N/2) = g(r)-\omega^r h(r). $$
Hence every transform of length $N$ is reduced to two transforms of length $N/2$, followed by the combinations
$$ f(r)=g(r)+\omega^r h(r), $$
$$ f(r+N/2)=g(r)-\omega^r h(r), \qquad 0\le r<N/2. $$
Repeating the same decomposition recursively reduces the problem to transforms of length $1$, which require no arithmetic. Therefore scheme (40) yields a complete algorithm for computing the discrete Fourier transform.
Let $T(N)$ denote the number of arithmetic operations on complex numbers.
For each $r$, the combination step requires:
- One multiplication to form $\omega^r h(r)$.
- One addition to obtain $f(r)$.
- One addition to obtain $f(r+N/2)$.
Thus $N/2$ complex multiplications and $N$ complex additions are required at each stage. Therefore
$$ T(N)=2T(N/2)+\frac N2+N =2T(N/2)+\frac{3N}{2}, $$
with
$$ T(1)=0. $$
Let $N=2^n$. At level $j$ of the recursion tree there are $2^j$ subproblems of size $N/2^j$, hence the work on that level is
$$ 2^j\cdot \frac{3}{2}\frac{N}{2^j} = \frac{3N}{2}. $$
There are $n=\log_2N$ levels, so
$$ T(N) = \frac{3N}{2}\log_2N. $$
More precisely,
$$ T(N) = \frac N2\log_2N \quad\text{complex multiplications} $$
and
$$ N\log_2N \quad\text{complex additions}. $$
Thus the discrete Fourier transform of length $N=2^n$ can be evaluated in
$$ \frac N2\log_2N+N\log_2N = \frac{3N}{2}\log_2N $$
arithmetic operations on complex numbers.
Verification
For $N=2$,
$$ f(0)=F(0)+F(1), \qquad f(1)=F(0)-F(1). $$
The recurrence gives
$$ \frac N2\log_2N=1 $$
complex multiplication and
$$ N\log_2N=2 $$
complex additions. The multiplication is by $\omega^0=1$ and may be regarded as trivial, matching the direct computation.
For general $N$, each recursion level combines pairs
$$ (g(r),h(r)) \mapsto \bigl(g(r)+\omega^r h(r),, g(r)-\omega^r h(r)\bigr), $$
producing exactly the values required above. Since the recursion terminates at transforms of length $1$, every value $f(s)$ is computed exactly once.
Notes
This is the radix-$2$ Cooley-Tukey fast Fourier transform. The direct evaluation of
$$ f(s)=\sum_{0\le t<N}F(t)\omega^{st} $$
requires $N^2$ complex multiplications and approximately $N(N-1)$ complex additions. The recursive method reduces the complexity to
$$ O(N\log N), $$
which is exponentially smaller in the parameter $n=\log_2N$.
$$ \boxed{\text{FFT cost }= \frac N2\log_2N\ \text{complex multiplications} + N\log_2N\ \text{complex additions}} $$