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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用