The Fast Fourier Transform

The Fast Fourier Transform computes the DFT quickly. This important algorithm for computer science (not only computer algebra, but also digital signal processing for instance) was (re)-discovered in 1965 by Cooley and Tukey.

Let n mathend000# be a positive even integer, $\omega$ $\in$ R mathend000# be a primitive n mathend000#-th root of unity and f = $\Sigma_{{{0 \, \leq \, i \, < \, n}}}^{{}}$ f_i xⁱ mathend000#. In order to evaluate f mathend000# at 1,$\omega$,$\omega^{{2}}_{{}}$,...,$\omega^{{{n-1}}}_{{}}$ mathend000#, we follow a divide-and-conquer strategy; more precisely, we consider the divisions with remainder of f mathend000# by x^n/2 - 1 mathend000# and x^n/2 + 1 mathend000#. So let q₀, q₁, r₀, r₁ mathend000# be polynomials such that

$$\left\{\vphantom{ \begin{array}{cc} {\deg}(r_0) < n/2 \\ {\deg}(q_0) < n/2 \end{array} }\right. \begin{array}{cc} {\deg}(r_0) < n/2 \\ {\deg}(q_0) < n/2 \end{array}$$ (31)

and

$$\left\{\vphantom{ \begin{array}{cc} {\deg}(r_1) < n/2 \\ {\deg}(q_1) < n/2 \end{array} }\right. \begin{array}{cc} {\deg}(r_1) < n/2 \\ {\deg}(q_1) < n/2 \end{array}$$ (32)

The relations deg(q₀) < n/2 mathend000# and deg(q₁) < n/2 mathend000# hold because the polynomial f mathend000# has degree less than n mathend000#. Observe that the computation of (q₀, r₀) mathend000# and (q₁, r₁) mathend000# can be done very easily. Indeed, let F₀, F₁ $\in$ R[x] mathend000# be such that

$$\left\{\vphantom{ \begin{array}{cc} {\deg}(F_1) < n/2 \\ {\deg}(F_0) < n/2 \end{array} }\right. \begin{array}{cc} {\deg}(F_1) < n/2 \\ {\deg}(F_0) < n/2 \end{array}$$ (33)

We have

f  =  F₁(x^n/2 -1) + F₀ + F₁    and    f  =  F₁(x^n/2 +1) + F₀ - F₁ (34)

Hence we obtain

r₀  =  F₀ + F₁    and    r₁  =  F₀ - F₁ (35)

Let i mathend000# be an integer such that 0 $\leq$ i < n/2 mathend000#. By using Relation (31) with x = $\omega^{{{2 \, i}}}_{{}}$ mathend000# we obtain

$$\omega^{{{2 \, i}}}_{{}} \omega^{{{2 \, i}}}_{{}} \omega^{{{n \, i}}}_{{}} \omega^{{{2 \, i}}}_{{}} \omega^{{{2 \, i}}}_{{}}$$ (36)

since $\omega^{{{n \, i}}}_{{}}$ = 1 mathend000#. Then, by using Relation (32) with x = $\omega^{{{2 \, i + 1}}}_{{}}$ mathend000# we obtain

$$\omega^{{{2 \, i + 1}}}_{{}} \omega^{{{2 \, i + 1}}}_{{}} \omega^{{{n \, i}}}_{{}} \omega^{{{n/2}}}_{{}} \omega^{{{2 \, i + 1}}}_{{}} \omega^{{{2 \, i + 1}}}_{{}}$$ (37)

since $\omega^{{{n/2}}}_{{}}$ = - 1 mathend000#. Indeed, this last equation follows from

$$\omega^{{{n}}}_{{}} \omega^{{{n/2}}}_{{}} \omega^{{{n/2}}}_{{}}$$ (38)

and the fact that $\omega^{{{n/2}}}_{{}}$ - 1 mathend000# is not zero nor a zero divisor. Therefore we have proved the following

Proposition 4   Evaluating f $\in$ R[x] mathend000# (with degree less than n mathend000#) at 1,$\omega^{{1}}_{{}}$,...,$\omega^{{{n-1}}}_{{}}$ mathend000# is equivalent to

• evaluate r₀ mathend000# at the even powers $\omega^{{{2 \, i}}}_{{}}$ mathend000# for 0 $\leq$ i < n/2 mathend000#, and
• evaluate r₁ mathend000# at the odd powers $\omega^{{{2 \, i + 1}}}_{{}}$ mathend000# for 0 $\leq$ i < n/2 mathend000#.

Since it is easy to show that $\omega^{{2}}_{{}}$ mathend000# is a primitive n/2 mathend000#-th root of unity we can hope for a recursive algorithm. This algorithm would be easier if both r₀ mathend000# and r₁ mathend000# would be evaluated at the same points. So we define

$$\omega^{{{2 \, i}}}_{{}} \omega^{{{2 \, i + 1}}}_{{}}$$ (39)

Now we obtain the following algorithm.

Algorithm 1  

mathend000#

Theorem 1   Let n mathend000# be a power of 2 mathend000# and $\omega$ $\in$ R mathend000# be a primitive n mathend000#-th root of unity. Then Algorithm 1 computes DTF_$\omega$(f ) mathend000# using

• n log(n) mathend000# additions in R mathend000#,
• (n/2) log(n) mathend000# multiplications by powers of $\omega$ mathend000#.

leading in total to 3/2 n log(n) mathend000# ring operations.

Proof. By induction on k = log₂(n) mathend000#. Let S(n) mathend000# and T(n) mathend000# be the number of additions and multiplications in R mathend000# that the algorithms requires for an input of size n mathend000#. If k = 0 mathend000# the algorithm returns (f₀) mathend000# whose costs is null thus we have S(0) = 0 mathend000# and T(0) = 0 mathend000# which satisfies the formula since log(n) = log(1) = 0 mathend000#. Assume k > 0 mathend000#. Just by looking at the algorithm we that

S(n)  =  2 S(n/2) + n    and    T(n)  =  2 T(n/2) + n/2 (40)

leading to the result by plugging in the induction hypothesis. $\qedsymbol$