[1]王元明.W矩阵与FFT[J].东南大学学报(自然科学版),1979,9(1):117-126.[doi:10.3969/j.issn.1001-0505.1979.01.009]
 Wang Yuan-Ming.Matrix w and FFT[J].Journal of Southeast University (Natural Science Edition),1979,9(1):117-126.[doi:10.3969/j.issn.1001-0505.1979.01.009]
点击复制

W矩阵与FFT()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
9
期数:
1979年第1期
页码:
117-126
栏目:
本刊信息
出版日期:
1979-03-20

文章信息/Info

Title:
Matrix w and FFT
作者:
王元明
undefined
Author(s):
Wang Yuan-Ming
关键词:
变换矩阵 非零元素 分解式 稀疏矩阵 快速算法 计算量 快速计算 乘法运算 程序计算 证明
分类号:
+
DOI:
10.3969/j.issn.1001-0505.1979.01.009
摘要:
本文首先研究了离散傅里哀变换(DFT)的变换矩阵(简称为W矩阵)的分解问题,证明了N=2~n阶的W矩阵可以分解成n个稀疏矩阵(每行只有两个非零元素)的乘积。然后利用所获得的分解式给出了一种快速计算DFT的方法,并对用这种方法计算DFT所需要的总计算量作了精确的统计。
Abstract:
This paper first discusses the question of factorization of matrix W of the discrete Fourier transform and proves that the 2~n×2~n matrix W_N, obtained by appropriate reordering of the rows of W, can be factored into a product of n spare matrices (where every row has only two nonzero entries). This provides a new rapid algorithm for the computation of discrete Fourier transform, and the precise number of operations for this method is also given.
更新日期/Last Update: 2013-05-01