中国科学技术大学：《并行计算 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非递归算法

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr DFT的顺序代码 代码1 代码2 for j=o to n-1 do W=w bj]=0 for j=o to n-1 do for k=o to n-1 do []=0 S=00 b[jb[j]+wkJa[k for k=o to n-1 do end for b[J=b[J]+s*a[k] end for S=SW 注:代码1需要计算uJ end for 代码2的复杂度为O(n2) W=WW end for 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 7 2021/2/19 DFT的顺序代码 ▪ 代码1 for j=0 to n-1 do b[j]=0 for k=0 to n-1 do b[j]=b[j]+ωk*ja[k] end for end for 注：代码1需要计算ωk*j 代码2的复杂度为O(n2) ▪ 代码2 w=ω0 for j=0 to n-1 do b[j]=0, s=ω0 for k=0 to n-1 do b[j]=b[j]+s*a[k] s=s*w end for w=w*ω end for

中国料学火计算机科学与波术系 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非递归算法

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 串行FT递归算法 ■蝶式递归计算原理 令O=已2x1m2)为n/2次单位元根,则有O=O 将b向量的偶数项(b,b2,bn2)和奇数项(b,b3bn)分别记为 (b,2)和(b,b…,b 注意推导中反复使用O"=1,om2 3 4 8 (1,0) 7 国家高性能计算中心(合肥 O=(0,-1)2021/2/19

国家高性能计算中心（合肥） 9 2021/2/19 串行FFT递归算法 ▪ 蝶式递归计算原理 令 为n/2次单位元根，则有 . 将b向量的偶数项 和奇数项 分别记为 和 注意推导中反复使用 ~ 2 i /(n / 2) e  ＝ ~ 2 ＝ T n (b ,b ,...,b ) 1 3 −1 T (b ,b ,...,bn ) 0 1 1 2 −    T (b ,b ,...,bn ) 0 1 1 2 −    1, 1, 1, , n n/ 2 l n s n p p  =  = −  =  = + ω8 =(1,0) ω6 =(0,-i) ω2 =( 0,i) ω4 =(-1,0) ω7 ω3 ω5 ω1 图11.1 T n (b ,b ,...,b ) 0 2 −2

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 串行FT递归算法 偶数时:b=b=∑ o d k=0 +oa+0 a+...+0 a., a. +a + a (ao+a2)+(a1+a1)+o(a2+a+2)+ (-1 (a1+an1) (ao+a2)+o(a1+a4+1)+o(a2+a2+2)+ (a, +a ∑o( 1=0,1, 因此,向量(bnx…,b2)是(a0+a241+41x,41+an)的DFT 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 10 2021/2/19 串行FFT递归算法 ( ) ( ) ( ) ( ) b b b a a a a a a DFT a a l a a a a a a a a a a a a a a a a a a a a a a a a b b a T n T n n k k k k l n l l l n l l l n l l l l l l n k k l k l l n n n n n n n n n n n n n n n n n n n n n 因此，向量 是 的 偶数时： ( , ,..., ) ( , ,..., ) ( ) 0,1, , 1 ~ ( ) ~ ( ) ~ ( ) ~ ( ) ( ) ( ) ( ) ( ) 0 2 2 0 1 1 1 1 2 1 0 1 1 1 2 2 2 0 1 1 1 1 2 1 2 2 4 1 1 2 0 1 2 1 2 4 1 2 1 2 1 2 4 1 2 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 − + − − − = + − − − + + − − − + + − − + + − − − = + + + = + = − + + = + + + + + + + + = + + + + + + + + + + = + + + + +  = =                     

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 串行FT递归算法 奇数时:b"=b2=∑ 2+1)k =a0+Oa1+ 2(2/+1) (-121+1) a.,+ (2/+1 (+12/+1) a +o a.,+…+O (n-1)(2l+1) a0+o 0a,+002a+or(e202-ag-1 a -o ad +1 (ao-a4)+OO(a1-a2)+o-( +oo(a1-a1)+2o2( ∑bo'(a4-ak) 7=0,1,…,2-1 k=0 因此,向量(b,b3,…,bh)是(a0-a1)O(a1-a41)…,O(a41-an)的DFT 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 11 2021/2/19 串行FFT递归算法 ( ) ( ) ( ) ( ) ( ) ( ) ( ) b b b a a a a a a DFT a a l a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a b b a T n T n n k k k k l k n l l l n l l l n l l l l l n n l l l l l l n k k l k l l n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n 因此，向量 是 的 奇数时： ( , ,..., ) (( ), ( ),..., ( )) ( ) 0,1, , 1 ~ ( ) ~ ( ) ~ ( ) ~ ( ) ( ) ( ) ( ) ( ) 1 1 1 1 3 1 0 1 1 2 1 0 1 1 1 1 2 2 2 2 0 1 1 1 1 2 1 1 2 2 4 2 1 1 2 0 1 2 1 1 1 2 1 2 1 1 2 4 2 1 2 0 1 1 (2 1) 1 (2 1) 1 (2 1) 1 1 (2 1) 2 2(2 1) 1 2 1 0 1 0 (2 1) 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 − − − − + − = + − − − − + + − − − − + + − − − + − − − − − + + + + + − + + − + − = + + − − − = − = − = − + − + − + + − = − + − + − + + − − − − = + + + + − + + + = + + + + + = =                                          