二维离散傅里叶变换DFT（2^n;2）计算复杂性与张量乘积

Computative Complexity of Two-Dimensional Disctete Fourter Transform DFT (2~n;2)and Tensor Products

本文从(?)单代数中的直和、张量乘积与离散傅里叶变换之间的关系出发,提出用直和、张量乘积表示的二维离散傅里叶变换DFT(2(?))各种算法的矩阵表示式。这种矩阵张量乘积表示式不仅揭示了各种DFT((?)2)算法之间内在联系和便于比较它们的计算复杂性,而且给出获得最小乘法次数的DFT(2(?)2)算法的途径,从而从理论上论证计算DFT(2(?)2)所需的最小实数乘法次数为2(?)-3n2(?)+3.2(?)+8。

In this papet we develop the expression of tensor products of matrices of various two-dimensional discrete Fourier transform algorithms from a point of view that direct sums and tensor products of Abelian semi-simple algebras had a deep relation to compute discrete Fourier transforms. This unified expression of tensor products of matrices not only delineates the inherent relationship between various DFT (2(?); 2) algorithms and gives their computative complexity bat also gives the ways to construct the minimal multiplications algorithm to compute DFT (2(?);2). Therefore, it leads to demonstrate the minimal number of real multiplications necessary to compute DFT (2(?); 2) theoretically.