Towards an iterative algorithm for the DTF

We first change the intermediate polynomials. Let $ n=2^r$ be a power of $ 2$ , let $ {\omega} \in R$ be a primitive $ n$ -th root of unity and $ A(x) = {\Sigma}_{0 \, \leq \, i \, < \, n} \ a_i \, x^i$ . We define

\begin{displaymath}\begin{array}{rcl} A^{[0]}(x) & = & a_0 + a_2 x + a_4 x^2 + \...
... + a_3 x + a_5 x^2 + \cdots + a_{n-1} x^{n/2 -1} \\ \end{array}\end{displaymath} (55)

such that we have

$\displaystyle A(x) \ = \ A^{[0]}(x^2) + x \, A^{[1]}(x^2).$ (56)

Hence evaluating $ A$ at $ 1, {\omega}, {\omega}^2, \ldots, {\omega}^{n-1}$ is reduced to evaluate $ A^{[0]}$ and $ A^{[1]}$ at $ 1, {\omega}^2, {\omega}^4, \ldots, {\omega}^{2n-2}$ . But this second sequence of powers of $ {\omega}$ consists of two identical sequences of length $ n/2$ . Indeed, for every integer $ k$ we have

$\displaystyle ({\omega}^{k+ n/2})^2 \ = \ ({\omega}^{k})^2$ (57)

Since $ {\omega}^{k} (1 - {\omega}^{n/2}) \neq 0$ holds, we obtain

$\displaystyle {\omega}^{k+ n/2} \ = \ - {\omega}^{k}$ (58)

Hence we only need to evaluate $ A^{[0]}$ and $ A^{[1]}$ at

$\displaystyle 1, {\omega}^2, {\omega}^4, \ldots, {\omega}^{n-2}.$ (59)

This provides us directly with the values of $ A$ at

$\displaystyle 1, {\omega}, {\omega}^2, \ldots, {\omega}^{n/2-1}$ (60)

and the values of $ A$ at

$\displaystyle {\omega}^{n/2}, {\omega}^{n/2+1}, \ldots, {\omega}^{n-1}$ (61)

by using the fact these numbers are respectively equal to

$\displaystyle -1, -{\omega}, -{\omega}^2, \ldots, -{\omega}^{n/2-1}.$ (62)

To summarize, for $ 0 \leq i \leq n/2 -1$ we have

\begin{displaymath}\begin{array}{rcl} A({\omega}^i) & = & A^{[0]}({\omega}^{2i})...
...ga}^{2i}) - {\omega}^i \, A^{[1]}({\omega}^{2i}) \\ \end{array}\end{displaymath} (63)

Algorithm 3  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $n = 2^r$...
...n/2}$\ := $y_k^{[0]} - t$\ \\
\> {\bf return} $y$
\end{tabbing}\end{minipage}}

The validity of Algorithm 3 follows from the two following observations. Observe that the recursive calls of $ DFT(n,A,{\Omega})$ defines an ordering of the coefficients of $ A$ shown on Figure 2 for $ n=8$ . Let us call this ordering the DFT ordering of $ A$ .

Observe that if the input array $ A$ is sorted w.r.t. this DFT ordering, one can describe easily the recursive calls with a binary tree. If this tree is traversed bottom-up, from left to right, we are led to an iterative algorithm working in place! For instance, for $ n=8$ , assuming that the input array $ A$ is

$\displaystyle \mid a_0 \mid a_4 \mid a_2 \mid a_6 \mid a_1 \mid a_5 \mid a_3 \mid a_7 \mid$    

We obtain the desired result in $ A$ using the following straigth-line program
  1. $ a$ := $ a_0$
  2. $ b$ := $ a_1$
  3. $ a_0$ := $ a + b$
  4. $ a_1$ := $ a - b$
  5. $ a$ := $ a_2$
  6. $ b$ := $ a_3$
  7. $ a_2$ := $ a + b$
  8. $ a_3$ := $ a - b$
  9. $ a$ := $ a_4$
  10. $ b$ := $ a_5$
  11. $ a_4$ := $ a + b$
  12. $ a_5$ := $ a - b$
  13. $ a$ := $ a_6$
  14. $ b$ := $ a_7$
  15. $ a_6$ := $ a + b$
  16. $ a_7$ := $ a - b$
  17. $ a$ := $ a_0$
  18. $ b$ := $ a_1$
  19. $ c$ := $ a_2$
  20. $ d$ := $ a_3$
  21. $ a_0$ := $ a + c$
  22. $ a_2$ := $ a - c$
  23. $ a_1$ := $ b + {\omega} d$
  24. $ a_3$ := $ b - {\omega} d$
  25. $ a$ := $ a_4$
  26. $ b$ := $ a_5$
  27. $ c$ := $ a_6$
  28. $ d$ := $ a_7$
  29. $ a_0$ := $ a + c$
  30. $ a_2$ := $ a - c$
  31. $ a_1$ := $ b + {\omega} d$
  32. $ a_3$ := $ b - {\omega} d$
  33. $ a$ := $ a_0$
  34. $ b$ := $ a_1$
  35. $ c$ := $ a_2$
  36. $ d$ := $ a_3$
  37. $ e$ := $ a_4$
  38. $ f$ := $ a_5$
  39. $ g$ := $ a_6$
  40. $ h$ := $ a_7$
  41. $ a_0$ := $ a + e$
  42. $ a_1$ := $ b + {\omega} f$
  43. $ a_2$ := $ c + {\omega}^2 f$
  44. $ a_3$ := $ d + {\omega}^3 h$
  45. $ a_4$ := $ a + e$
  46. $ a_5$ := $ b - {\omega} f$
  47. $ a_6$ := $ c - {\omega}^2 f$
  48. $ a_7$ := $ d - {\omega}^3 h$

Figure 2: Recursive calls for $ n=8$ .
\begin{figure}\htmlimage
\centering
\includegraphics[scale=.5]{fft8.eps}\end{figure}

Algorithm 4  

\fbox{
\begin{minipage}{12 cm}
\begin{description}
\item[{\bf Input:}] $n = 2^r$...
...k + j + m/2]$\ := $u - t$\ \\
\> {\bf return} $A$
\end{tabbing}\end{minipage}}

Remark 8   To get the DFT ordering for $ A$ , that is $ [a_0, a_4, a_2, a_6, a_1, a_5, a_3, a_7]$ , observe that this ordering changes

$\displaystyle 000, 001, 010, 011, 100, 101, 011, 111$ (64)

to

$\displaystyle 000, 100, 010, 110, 001, 101, 110, 111$ (65)

Remark 9   The ring $ {\mbox{${\mathbb{Z}}$}}$ does not have any interesting roots of unity. In order to take advantage of the FFT-based multiplication one could use a modular approach as follows.

Marc Moreno Maza
2008-01-07