中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（PPT课件讲稿）第三篇 并行数值算法 第十一章 快速傅里叶变换

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第三篇并行数值算法 第八章基本通讯操作 第九章稠密矩阵运算 第十章线性方程组的求解 第十一章快速傅里叶变换

第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第十一章快速傅里叶变换 111快速傅里叶变换 11.2并行FT算法

第十一章 快速傅里叶变换 11.1 快速傅里叶变换 11.2 并行FFT算法

中国料学火计算机科学与波术系 riversity of Science and Technolocy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 111快速傅里叶变换(FFT 111.1离散傅里叶变换(DFT 1112DFT的顺序代码 111.3串行FFT递归算法 111.4串行FFT井递归算法

11.1 快速傅里叶变换(FFT) 11.1.1 离散傅里叶变换(DFT) 11.1.2 DFT的顺序代码 11.1.3 串行FFT递归算法 11.1.4 串行FFT非递归算法

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 离散傅里叶变换(DFT) 定义 给定向量A=(a,q1,…an1),DFT将A变换为B=(bo,b1…,bn1)T a,0 0≤j≤n-1 这里O=e2m为n次单位元根,i=√-1;写成矩阵形式为 b 0 (n-1)(n-1) 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 5 2021/2/19 离散傅里叶变换(DFT) ▪ 定义 给定向量A=(a0 ,a1 ,…,an-1 ) T,DFT将A变换为B=(b0 ,b1 ,…,bn-1 ) T                           =             = − =   − − − − − − − − − =  1 1 0 0 1 2( 1) ( 1)( 1) 0 1 2 1 0 0 0 0 1 1 0 2 / 1 0 1; 0 1 n n n n n n n i n n k kj j k a a a b b b e n i b a j n                         这里 ＝  为 次单位元根， 写成矩阵形式为 即

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 111快速傅里叶变换(FFT 1111离散傅里叶变换(DFT) 1112DFT的顺序代码 111.3串行FFT递归算法 111.4串行FFT井递归算法

11.1 快速傅里叶变换(FFT) 11.1.1 离散傅里叶变换(DFT) 11.1.2 DFT的顺序代码 11.1.3 串行FFT递归算法 11.1.4 串行FFT非递归算法