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.

taocpmathematicsalgorithmsvolume-2hm-hard

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:

  1. One multiplication to form $\omega^r h(r)$.
  2. One addition to obtain $f(r)$.
  3. 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}} $$