复杂傅里叶级数的机器计算算法

复数傅里叶级数的计算机算法Yates提出的计算2m交叉阶乘的有效方法已闻名，而Box将其推导至3m的情况。Good总结了这些方法并且给出了一个可以用于计算傅里叶级数的漂亮算法。在他们完整的总结中，Good的方法可以应用于解决用可被分解成m（m正比于㏒N）个稀疏矩阵的N×N阶矩阵乘以N维向量的这一类问题。结果是这个过程所需的计算数量正比于N㏒2N而不是N2。这种方法下面用于计算复杂傅里叶级数。这方法的有用性体现在数据量是或可被选择为高阶复数时。这种算法在这篇文章里将被以相当不同的形式推出和呈现。特别是N的选取，使用N=2m时二进制计算机的特殊优势将被体现，且整个计算能在给定傅里叶系数的N维存储空间内进行。考虑计算下式的傅里叶级数给定傅里叶系数A（k）是复数，W是N次主方根，直接使用（1）计算需要N2次计算（此时计算意味复数乘法与复数加法）。这里描述的算法在给定傅里叶复振幅组成的数组上重复并且结果是少于2N㏒2N次计算和除所给数组A之外不再需要更多数据存储空间。为推演这个算法，考虑合数N，例如N=r1·r2，那么（1）中的指数可以表达为然后可以写出因为与k1的内积只与j0和k0有关，可以被定义为一个新数组，结果可写成数组A1中有N个元素，每个需要做r1次计算，获得A总共需要Nr1次计算。类似的，根据A1计算X需要Nr2次计算。所以，（6）（7）这两步算法共需要次计算。从它在（6）的应用可以容易看出这个过程的成功，给出一个m级的算法要求次计算，其中如果rj=sjtj,且sjtj1,那么sj+tjrj除非sj=tj=2,其中sj+tj=rj。总之使用尽可能多的因子使（9）最小，但是因子2成对结合没有损失。如果N可以选择为高阶复数，我们可以得到很好的增益。如果所有的r等于r,那么，从（10）我们得到和所有计算数是如果N=rmsntp那么我们发现因此是以下数的加权平均值这些数的值如下rj=3的使用理论上是最有效的，但是增益只有2和4的6%，而使用2和4有其他的优势。如果有必要，范围至10的rj的使用只会增加少于50%的计算量。因此，我们可以发现N的“高阶复数”值，满足只是任何大数的百分之几。如果可能，N=rm在r=2或4中的使用会为使用二进制计算的电脑在存储和计算效率上提供很多优势。r=2的算法从由将指数写成以下形式推出其中jv和kv等于0或1，且是j和k在二进制表示时对应位上的内容。所有矩阵可以被写成他们指数的位运算。这样（1）可以写成kv等于0或1，因为（15）中最内部的和基于km-1,只与j0,km-2,…,k0有关，可被写成继续到下一个基于km-2的最内部的和并使用得到接下来的一系列数组其中l=1,2,…,m和为根据指数守恒，它将被存储在指数如下的位置(20)式表明，只有两个指数位是0或者1的在2m-l比特位的存储单元被用于计算需要。因为(20)式所示的运算操作，只要借助j0,…jl-2和k0,…km-l-1的值，就能够被同时完成，所以可以进行并行运算。在一些应用中，我们可以很方便地使用(20)式,用Al-2的表达式来表示Al，也就是得到r=4时的等效表达式。通过将X中所示的下标在二进制意义上的反转之后，我们就可以得到数组Am中的下标了。在一些应用中，傅里叶和需要计算2次，以上的过程就能被程序化，所以位反转就没有必要了。例如，考虑以下差分方程的解：已有的方法可以用来计算方程解的傅里叶幅值解的傅里叶幅值是B(k)和A(k)数组的顺序经过位反转，但是通过对(20)式的修改，我们可以由A(k)得到正确的下标。一个基于以上方法的用于计算三维傅里叶和的程序已经编写好并被用于IBM7094。计算一个2a×2b×2c数组的计算时间显示如下：IBM华盛顿研究中心纽约州约克城高地贝尔电话实验室缪勒海尔，新泽西州普林斯顿大学普林斯顿，新泽西州3090104662理工平台沈奕琛