下载此文档

并行计算实验指导(9)版.doc


文档分类:IT计算机 | 页数:约14页 举报非法文档有奖
1/14
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/14 下载此文档
文档列表 文档介绍
并行计算实验指导(9)版.doc支持免费共享
10快速傅氏变换和离散小波变换
长期以来,快速傅氏变换(Fast Fourier Transform)和离散小波变换(Discrete Wavelet Transform)在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及 概率论等领域中都得到了广泛的应用。各种快速傅氏变换(FFT)和离散小波变换(DWT)算法 不断出现,成为数值代数方面最活跃的一个研究领域,而其意义远远超过了算法研究的范围, 进而为诸多科技领域的研究打开了一个崭新的局面。本章分别对FFT和DWT的基本算法作 了简单介绍,若需在此方面做进一步研究,可参考文献[2]。

离散傅里叶变换是20世纪60年代是计算复杂性研究的主要里程碑之一,1965年Cooley 和Tukey所研究的计算离散傅里叶变换(Discrete Fourier Test)的快速傅氏变换(FFT)将计算量 从0(,)下降至o("log"),推进了 FFT更深层、更广法的研究与应用。FFT算法有很多版本, 但大体上可分为两类:迭代法和递归法,本节仅讨论迭代法,递归法可参见文献[1]、[2]。

假定a[0],a[l], -,a[n-l]为一个有限长的输入序列,址0],址1],…,址"-]]为离散傅里叶
n—\ 2 加 _
变换的结果序列,则有:处]=丫“[口W”"”(k = 0」2…,"-1),其中W„ = eV,实际上,上式可 m=0
写成矩阵W和向量d的乘积形式:
bo
w。 w。 w° …w°
°0
ypO ypl yp2 … w” 一 1
a\
方2

W。 w2 Vf4 .. • w2(" -1)
ypO yp(n-l) w2(«-l) ••• vp(n-l)(n-l)
^n-1
一般的n阶矩阵和n维向量相乘,计算时间复杂度为"2,但由于W是一种特殊矩阵, 故可以降低计算量。,其串行算法如下:

输入:a=(a0,au …,a”“)
输出:血=血01,…0”一1)
Begin
for k=0 to n-1 do
c^ak
end for
for /z=logn-l downto 0 do
p=2"
q=n/p
z=wq,~
for k=0 to n-1 do
if (k mod p=k mod2p) then
Q = Q + Q+p
Q+p=( Ck - Ck+p)z k mod” /* Ck 不用⑴计算的新值 */
end if
end for
end for
for k=l to n-1 do
b© = Ck /* T(k)为 k 的位反 */
end for
End
b2
方3
显然,FFT算法的计算复杂度为0(加og〃)。

设P为处理器的个数,一种并行FFT实现时是将n维向量a划分成p个连续的m维子 向量,这里m = \n / 79~|,第i个子向量中下标为iXm, •••, (z+l)X/?z-l,其元素被分配至第i 号处理器(=0丄…,p-1)。,FFT算法由log"步构成,依次以210gn-\ 2logn-2 2、1为下标跨度做蝶式计算,我们称下标跨度为2"的计算为第%步(7i=logn-7,
log"-2,…,1, 0)。并行计算可分两阶段执行:第一阶段,第logW-l步至第logm步,由于下 标跨度hN m,各处理器之间需要通信;第二阶段,第logm-1步至第0步各处理器之间不 需要通信。具体并行算法框架描述如下:
FFT并行算法
输入:d=(a(),ai,…,a”一J
输出:Z?=(Z?O01, •••A-1)
Begin
对所有处理器my_rank(my_rank=O,•••,/?-1)同时执行如下的算法:
for h=\ogp-l downto 0 do
/*第一阶段,第logn-1步至第logm步各处理器之间需要通信*/
t=® ,Z=2(/+10gZM),q=nll, , j= j+1 ,v=27 /*开始戸0*/
if ((my rank mod ^)=(my_rank mod 2t)) then
/*本处理器的数据作为变换的前项数据*/
tt= my_rank+p/v
接收由力号处理器发来的数据块,并将接收的数据块存于
c[my_rank*m+n/v]至寸 c[my_rank*m+n/v+m]
for k=0 to m-1 do
c [k]=c [k] +c [k-^-n/v

并行计算实验指导(9)版 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数14
  • 收藏数0 收藏
  • 顶次数0
  • 上传人蓝天
  • 文件大小176 KB
  • 时间2021-10-25