(多维快速傅里叶变换)我们可以定义的一维离散傅里叶变换推广

 (多维快速傅里叶变换)我们可以定义的一维离散傅里叶变换推广到d维上。这时输人是一个d维的数组A=(a_j1,a_j2,...,a_jd),维数分别为n1,n2,...,nd,其中n1n2...nd=n。

定义d维离散傅里叶变换如下: 

                                       

a. 证明:  我们可以依次在每个维度上计算一维的DFT来计算一个d维的DFT。也就是说，首先沿着第1维计算n/n1个独立的一维DFT。然后，把沿着第1维的DFT结果作为输人，我们计算沿着第2维的n/n2个独立的一维DFT。利用这个结果作为输人，  我们计算沿着第3维的n/n3个独立的一维DFT,  如此下去，  直到第d维。
b.证明:  维度的次序并无影响，于是可以通过在d个维度的任意顺序中计算一维DFT来 计算一个d维的DFT。
c.证明:  如果采用计算快速傅里叶变换计算每个一维的DFT,那么计算一个d维的DFT的总时间是O(nlgn),与d无关。