一种关于复杂傅里叶序列的机械计算的算法.docVIP

一种关于复杂傅里叶序列的机械计算的算法 James W.Cooley and John W.Tukey Yates介绍了一种关于计算2^m因子交互实验的有效方法，并以他的名字所闻名。对3^m点DFT的概括由Box et al给出。古德概括了这些方法并且给出了用于计算的优化的算法，其中一种就是傅里叶序列的计算。在整个推导过程中，我们必须用一个N×N的矩阵乘一个N维向量，这个N×N的矩阵可以被分解为m个稀疏矩阵，其中m与logN成正比，以此解决特定的问题。这个过程需要进行的操作次数为NlogN而不是N^2。在这里，我们用以上方法来计算复傅里叶序列。数据点数量为合数或者修改为合数时这种方法非常有用。这里我们用一种与众不同的方法推导出这种运算法则。需要注意的是N的选择。这里我们会展示令N 2m利用二进制计算机带来的特殊优势和整个计算过程，对于所给出的傅里叶系数这个过程只需N个数据存储位置就能进行。 考虑复傅里叶序列的计算问题 其中所给的傅里叶系数A k 为复数并且W是1的首要N次根， 如果利用 1 式直接进行计算，需要N2次操作，这里的“操作”是指在复数相加之后的复数的乘法，以下“操作”均为此意。 在下述的算法中，对所给的复傅里叶幅值进行迭代，在少于2Nlog2N次操作就能得到结果，并且过程中需要的数据存储位置数比存储所给的序列A所需的数量少。为了推到出改方法，假设N是合数，也就是N r1·r2。 1 中的就可以表示为 然后可以得到 因为 对k1的求和只依赖于j0和k0并且可以被定义为一个新的序列 序列A1中有N个元素，每一个需要r1次操作，共需要Nr1次操作来得到A1。地，需要Nr2次操作来从A1中计算X。因此，这个由 6 和 7 给出的两步算法，总共需要的操作次数为 在下面的过程中我们会看到以上方法运用的优势。首先对 6 进行运算，一个m步运算方法需要进行的操作次数如下 其中 如果rj sjtj并且sj,tj 1，除非sj+tj rj时sj tj 2，那么sj+tj rj。，再利用足够多的因数可以得到 9 的最小值，但是2的因数可以全部配对。如果我们能够选择一个高度复合的合数N，我们能得到非常实际的效果。如果所有的rj都等于r，那么根据 10 有 总的操作次数为 如果N rmsntp···,然后我们可以得到 因此 这些值的加权平均值为 的数值 可以看出用rj 3是最高效的，效率仅比用2或4高大约6%但用2或4有其他的。如果需要的话，利用10以内范围的数值可以提高不多于50%。因此，我们可以从任意给定的较大的数值的百分之几范围中找到数值“高度复合”的N。 对于二进制算法计算机来说，在可利用该方法的方面，比如说编址或经济，r 2或4时N rm的利用带来了重要的优势。 当r 2时，该算法可以由如下形式的系数推导得出 其中在j和k的二进制数中，其相对应的位的数值为jv和kv，其值等于0或1。现在所有的序列都可以写为他们的二进制数各位上数字的函数。根据这个约定 1 可以写为 其中的求和是kv从0到1。因为 15 最内层对km-1的求和，仅仅依赖于j0,km-2,···,k0，它可写为 然后进行次内层对km-2的求和，以此类推，再利用 就可以得到连续的序列 其中l 1,2, ···,m。 写出求和可以得到 根据的规定，它存放在以下式为的位置中 20 我们可以看，计算只牵扯到两个存储位置，它们的为由0和1组成的2m-1位二进制数。因为对于所有的j0,···,jl-2和k0,···,km-l-1， 20 所示的操作可以同时计算出结果，所以并行的运算是可行的。在某些应用中，用 20 来以Al-2的形式来表示Al是很方便的，并且可以得到和r 4的运算方法相等的结果。 最后计算的序列可以得到期望的傅里叶求和 因为这样一个顺序，要得到Am的必须对X的的二进制数进行逆序排列。 在一些应用中，傅里叶求和要算两次，上述的过程能够免去位反转的操作。例如，考虑如下微分方程的解 现有的方法是先利用如下公式算出傅里叶幅值 然后得到傅里叶幅值为 B k 和A k 序列是位逆序排列的，但是对 20 做一个明显的修改，A k 可以用来得到有正确的解。 基于上述方法计算三维傅里叶求和，我们已经为IBM7094编写好了一个程序。下面是计算一个三维数据点2a×2b×2c序列所需的时间： IBM 沃森研究中心 Yorktown Heights, New York 贝尔实验室 Murray Hill, New Jersey 普林斯顿大学 Princeton, New Jersey 1. G. E. P. BOX, L.R. CONNOR, W. R. COUSINS, O. L. DAVIES Ed. , F. R. HIRNSWORTH G. P. SILI