并行计算MPI程序设计

*******************实践教学*******************兰州理工大学理学院2016年春季学期并行计算课程专业班级：2013级信息与计算科学姓名：学号：指导教师：成绩：摘要FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。   设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）^2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）^2=N+N^2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog(2)(N)次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性关键字：FFT蝶式计算傅里叶变换目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc6"摘要PAGEREF_Toc6\h2HYPERLINK\l"_Toc7"目录PAGEREF_Toc7\h3HYPERLINK\l"_Toc8"一、题目及要求PAGEREF_Toc8\h4HYPERLINK\l"_Toc9"题目PAGEREF_Toc9\h4HYPERLINK\l"_Toc0"要求PAGEREF_Toc0\h4HYPERLINK\l"_Toc1"二、算法设计与算法原理PAGEREF_Toc1\h5HYPERLINK\l"_Toc2"算法原理与设计PAGEREF_Toc2\h5HYPERLINK\l"_Toc3"设计求解步骤PAGEREF_Toc3\h6HYPERLINK\l"_Toc4"三、算法描述与算法PAGEREF_Toc4\h7HYPERLINK\l"_Toc5"算法描述PAGEREF_Toc5\h7HYPERLINK\l"_Toc6"流程图PAGEREF_Toc6\h9HYPERLINK\l"_Toc7"四、源程序代码与运行结果PAGEREF_Toc7\h10HYPERLINK\l"_Toc8"源程序PAGEREF_Toc8\h10HYPERLINK\l"_Toc9"运行结果PAGEREF_Toc9\h16HYPERLINK\l"_Toc0"五、算法分析及其优缺点PAGEREF_Toc0\h17HYPERLINK\l"_Toc1"算法分析PAGEREF_Toc1\h17HYPERLINK\l"_Toc2"优缺点PAGEREF_Toc2\h18HYPERLINK\l"_Toc3"六、总结PAGEREF_Toc3\h19HYPERLINK\l"_Toc4"七、参考文献PAGEREF_Toc4\h20一、题目及要求题目对给定的α=（1,2，4，3，8，6，7，2），利用串行FFT递归算法(蝶式递归计算原理)计算其傅里叶变换的结果要求利用串行递归与蝶式递归原理，对给定的向量求解傅里叶变换的结果二、算法设计与算法原理算法原理与设计令为n/2次单位元根，则有.将b向量的偶数项和奇数项分别记为和注意推导中反复使用图设计求解步骤三、算法描述与算法流程算法描述n=8的FFT蝶式计算图图图FFT递归计算流程图流程图开始计算出前size_x/2个exp(-j*2π*k/size_x)个值，即W的值输入序列对应值（例如5+j3，输入53）输入序列长度size_x飞级数i>=QUOTE级数i加1是输出fft结果序列结束否该级该组起始下标j>=QUOTE计算出该级需要的W的个数l是否组起始下标加2*l该级该组元素序数k>=QUOTEK加1是X[j+k]X[j+k]lX[j+k+l]*W[(size_x/2/l)*k]X[j+k+l]-1否图四、源程序代码与运行结果源程序/************FFT***********/eal,&x[i].img);initW();eal=cos(2*PI/size_x*i);mg=-1*sin(2*PI/size_x*i);f",x[i].real);mg>=f\n",x[i].img);elseif(fabs(x[i].img)