(2. 4)for k=0 to n-l do if(k mod P=k mod2p) then (Ick=Ck+ Ck+p (i)lx+2=(ck-ck+p)kmo/*c不用()计算的新值* (3)for k-l to n-l do bn(6)=Ck/r(k)为k的位反* end fo 图1.1n=4时的FFT蝶式变换图 显然,FFT算法的计算复杂度为 O(nlogn)。 1.12并行FFT算法 设P为处理器的个数,一种并行FFT实现时是将n维向量a划分成p个连续的m维子 向量,这里m=「n/p,第i个子向量中下标为ⅸ×m,…,(计+1)×m-1,其元素被分配至第i 号处理器(=0,1,…,P1)。由图1.1可以看到,FFT算法由logn步构成,依次以21、 22、…、2、1为下标跨度做蝶式计算,我们称下标跨度为2"的计算为第h步(h=logn-l, logn-2,…,1,0)。并行计算可分两阶段执行:第一阶段,第logn-1步至第logm步,由于下 标跨度h≥m,各处理器之间需要通信:第二阶段,第logm-1步至第0步各处理器之间不 需要通信。具体并行算法框架描述如下: 算法222FFT并行算法 输入:a=(anan,…am1) 输出:b=(bb,…bn-) 对所有处理器 my rank( my rank=0,…,p-1)同时执行如下的算法 (I)for h=logp-I downton do(2.4) for k=0 to n-1 do if (k mod p=k mod2p) then (i)ck = ck + ck +p (ii)ck +p=( ck - ck +p)z k modp /* ck 不用(i)计算的新值 */ end if end for end for (3)for k=1 to n-1 do br(k) = ck /* r(k)为 k 的位反 */ end for End a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 b 0 b 4 b 2 b 6 b 1 b 5 b 3 b 7 0 0 0 0 0 0 2 2 1 2 3 0 图 1.1 n=4 时的 FFT 蝶式变换图 显然, FFT 算法的计算复杂度为 O(nlogn)。 1.1.2 并行 FFT 算法 设 P 为处理器的个数，一种并行 FFT 实现时是将 n 维向量 a 划分成 p 个连续的 m 维子 向量，这里 m = n / p ，第 i 个子向量中下标为 i×m, …, (i+1)×m-1，其元素被分配至第 i 号处理器（i=0,1, …, p-1）。由图 1.1 可以看到，FFT 算法由 logn 步构成，依次以 2 logn-1、 2 logn-2、…、2、1 为下标跨度做蝶式计算，我们称下标跨度为 2 h 的计算为第 h 步（h=logn-1, logn-2, …, 1, 0）。并行计算可分两阶段执行：第一阶段，第 logn-1 步至第 logm 步，由于下 标跨度 h≥ m，各处理器之间需要通信；第二阶段，第 logm-1 步至第 0 步各处理器之间不 需要通信。具体并行算法框架描述如下： 算法 22.2 FFT 并行算法 输入：a=(a0,a1, …,an-1) 输出：b=(b0,b1, …,bn-1) Begin 对所有处理器 my_rank(my_rank=0,…, p-1)同时执行如下的算法: (1)for h=logp-1 downto 0 do