11 快速傅里叶变换.ppt

文档介绍：并行计算
中国科学技术大学计算机科学与技术系
国家高性能计算中心(合肥)
2003年9月
2017/11/10
1
现代密码学理论与实践之五
第三篇并行数值算法 第八章基本通讯操作 第九章稠密矩阵运算 第十章线性方程组的求解 第十一章快速傅里叶变换
2017/11/10
2
现代密码学理论与实践之五
第十一章快速傅里叶变换 快速傅里叶变换 并行FFT算法
2017/11/10
3
现代密码学理论与实践之五
快速傅里叶变换(FFT) 离散傅里叶变换(DFT) DFT的顺序代码 串行FFT递归算法 串行FFT非递归算法
2017/11/10
4
现代密码学理论与实践之五
离散傅里叶变换(DFT)
定义
给定向量A=(a0,a1,…,an-1)T,DFT将A变换为B=(b0,b1,…,bn-1)T
2017/11/10
5
现代密码学理论与实践之五
快速傅里叶变换(FFT) 离散傅里叶变换(DFT) DFT的顺序代码 串行FFT递归算法 串行FFT非递归算法
2017/11/10
6
现代密码学理论与实践之五
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
2017/11/10
7
现代密码学理论与实践之五
快速傅里叶变换(FFT) 离散傅里叶变换(DFT) DFT的顺序代码 串行FFT递归算法 串行FFT非递归算法
2017/11/10
8
现代密码学理论与实践之五
串行FFT递归算法
蝶式递归计算原理
令为n/2次单位元根,则有.
将b向量的偶数项和奇数项分别记为
和
注意推导中反复使用
2017/11/10
9
现代密码学理论与实践之五
串行FFT递归算法
2017/11/10
10
现代密码学理论与实践之五