资源描述：
《并行计算实验指导(9)版》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、支持免费共享10快速傅氏变换和离散小波变换长期以来，快速傅氏变换(FastFourierTransfomi)和离散小波变换(DiscreteWaveletTransform)在数字信号处理、石汕勘探、地震预报、医学断层诊断、编码理论、量子物理及概率论等领域屮都得到了广泛的应川。各种快速傅氏变换(FFT)和离散小波变换(DWT)算法不断出现，成为数值代数方面故活跃的一个研究领域，而其意义远远超过了算法研究的范围,进而为诸多科技领域的研究打开了一个崭新的局血。本章分别对FFT和DWT的基本算法作了简单介绍，若需在此方面做进一步研究，可参考文献[2]。2.1快
2、速傅里叶变换FFT离散傅里叶变换是20世纪60年代是计算复杂性研究的主要里程碑之一，1965年Cooley和Tukey所研究的计算离散傅里叶变换(DiscreteFourierTest)的快速傅氏变换(FFT)将计算量从0(,)下降至O(/?log«),推进了FFT更深层、更广法的研究与应川。FFT算法有很多版木,但大体上可分为两类：迭代法和递归法，本节仅讨论迭代法，递归法可参见文献[1]、[2]。2.1.1串行FFT迭代算法假定a[0],°[l],—,a[n-l]为一个有限长的输入序歹U，方[0],b[l],・・・,恥・1]为离散傅里叶・・M2加变换的
3、结果序列，则h[k]='^a[k]W^伙=0,1,2,.../-1),其中W“=—,实际上，上式可zn=O写成矩阵W和向量G的乘积形式：ZI-17N=0w°w°…dobIVowl^2•・・dlbj■=■W2••…w2("-l)•••Cl2■•■"()••••VV(n-I)一1)•…yv(?j-l)(n-l)•-般的n阶矩阵和h维向量相乘，计算时间复杂度为斥，但由于W是一种特殊矩阵,故可以降低计算量。FFT的计算流图如图22.1所示,其串行算法如下:算法22.1单处理器上的FFT迭代算法输入：a=(a(),ah…如)输出：b=(bob,Begin(l)
4、fork=0ton-1doCk=akendfor(2)for/?=log/7-ldovvnto0doq=n/pz=wq/2fork=0ton-doif(kmodp=kmod2/?)then(i)Q=Q+Q+p(ii)Q+p=(Q-Q+p)/mOdZ；/*Ck不用⑴计算的新值*/endifendforendfor(3)for^=1to/?-!do/*r(k)为k的位反*/endforEnd000b()帖b2力6方1力5方3h7图22.1n=4时的FFT蝶式变换图显然,FFT算法的计算复杂度为0(/?log/7)o2.1.2并行FFT算法设P为处理器的个数
5、，一种并行FFT实现时是将n维向量。划分成〃个连续的m维子向量，这电m=[n/p~f第i个子向量屮下标为iXm,•••,(i+l)X加・1,其元素被分配至第i号处理器(归0丄…，/”1)。由图22」可以看到，FFT算法由logn步构成，依次以2k)gn-2呃「22、1为下标跨度做蝶式计算，我们称下标跨度为2〃的计算为第力步(/z=log/?-/,Iog/?-2,…，1,0)。并行计算可分两阶段执行：第一-阶段，第logn-1步至第logm步，由于下标跨度hM各处理器之间需要通信；第二阶段，第1007・1步至第0步各处理器之间不需要通信。具体并行算法框
6、架描述如下：算法22.2FFT并行算法输入：d=(d(),d
7、,…如)输出：b=(b(),bi,…,b“_i)Begin对所有处理器my_rank(my_rank=O,-••,/?-!)同时执彳亍如下的算法：for/?=logp・ldownto0do/*第一阶段，第Iog/7-l步至笫log/H步各处理器2间需要通信*/r=2G,/=2(,+los/M),q=n/l,z=wg,2,j=j+1,v=2y/*开始/=0*/if((my_rankmodr)=(my_rankm(xl2r))then/*本处理誥的数据作为变换的前项数据引tt=my_rank+p/
8、v接收由"号处理器发來的数据块，并将接收的数据块存于c[my_rank*m+n/v]SJc[my_rank*/n+n/v+zn]之中fork=0tom-1doc[k]=c[k]+c[k+n/v]ck+n/v]=(c[k]~C•[知讥,]'endfor将存于c[my_rank*/n+n/v]到c[my_rank*w+n/v+7n1之中的数据块发送到〃号处理器else/*本处理器的数据作为变换的后项数据*/将存于之中的数据块发送到my_nmk・#/y号处理器接收illniy_rank-/?/v号处理器发来的数据块存于c中endifendforfor/=lo
9、g/?z-ldownto0do/*第二阶段，第log/w-1步至第()步各处理器
