30-3 Multidimensional fast Fourier transform

We can generalize the $1$-dimensional discrete Fourier transform defined by equation $\text{(30.8)}$ to $d$ dimensions. The input is a $d$-dimensional array $A = (a_{j_1, j_2, \dots, j_d})$ whose dimensions are $n_1, n_2, \dots, n_d$, where $n_1n_2 \cdots n_d = n$. We define the $d$-dimensional discrete Fourier transform by the equation

$$y_{k_1, k_2, \dots, k_d} = \sum_{j_1 = 0}^{n_1 - 1} \sum_{j_2 = 0}^{n_2 - 1} \cdots \sum_{j_d = 0}^{n_d - 1} a_{j_1, j_2, \cdots, j_d} \omega_{n_1}^{j_1k_1}\omega_{n_2}^{j_2k_2} \cdots \omega_{n_d}^{j_dk_d}$$

for $0 \le k_1 < n_1, 0 \le k_2 < n_2, \dots, 0 \le k_d < n_d$.

a. Show that we can compute a $d$-dimensional $\text{DFT}$ by computing $1$-dimensional $\text{DFT}$s on each dimension in turn. That is, we first compute $n / n_1$ separate $1$-dimensional $\text{DFT}$s along dimension $1$. Then, using the result of the $\text{DFT}$s along dimension $1$ as the input, we compute $n / n_2$ separate $1$-dimensional $\text{DFT}$s along dimension $2$. Using this result as the input, we compute $n / n_3$ separate $1$-dimensional $\text{DFT}$s along dimension $3$, and so on, through dimension $d$.

b. Show that the ordering of dimensions does not matter, so that we can compute a $d$-dimensional $\text{DFT}$ by computing the $1$-dimensional $\text{DFT}$s in any order of the $d$ dimensions.

c. Show that if we compute each $1$-dimensional $\text{DFT}$ by computing the fast Fourier transform, the total time to compute a $d$-dimensional $\text{DFT}$ is $O(n\lg n)$, independent of $d$.

(Omit!)