An algorithm for the machine calculation of complex Fourier series
An algorithm for the machine calculation of complex Fourier series
复制标题
DOI：
10.1090/s0025-5718-1965-0178586-1
复制
发表时间：
1965-05
影响因子：
2
通讯作者：
J. Cooley;J. Tukey
中科院分区：
文献类型：
--
作者：
J. Cooley;J. Tukey
Yates提出了一种计算2'阶乘实验相互作用的有效方法，并以他的名字广为人知。Box等人（1）给出了对3'的推广。Good（2）推广了这些方法，并给出了优雅的算法，其中一类应用是傅立叶级数的计算。在它们的全部一般性中，Good的方法适用于某些问题，其中必须将N-向量乘以N X N矩阵，该矩阵可以分解为m个稀疏矩阵，其中m与log N成比例。这导致在一个程序中需要的操作数量与N log N而不是N2成比例。本文将这些方法应用于复傅里叶级数的计算。它们在数据点的数量是或可以选择为高度合成数的情况下很有用。该算法在这里推导和提出了一个相当不同的形式。注意N的选择。它还示出了如何特殊的优势，可以获得在使用的二进制计算机与N = 2'，以及如何整个计算可以在用于给定的傅立叶系数的N个数据存储位置的阵列内执行。考虑复傅里叶级数N-1（1）X（j）= EA（k）-Wjk，j = 0 1，*，N- 1，k=0的计算问题
An efficient method for the calculation of the interactions of a 2' factorial ex- periment was introduced by Yates and is widely known by his name. The generaliza- tion to 3' was given by Box et al. (1). Good (2) generalized these methods and gave elegant algorithms for which one class of applications is the calculation of Fourier series. In their full generality, Good's methods are applicable to certain problems in which one must multiply an N-vector by an N X N matrix which can be factored into m sparse matrices, where m is proportional to log N. This results inma procedure requiring a number of operations proportional to N log N rather than N2. These methods are applied here to the calculation of complex Fourier series. They are useful in situations where the number of data points is, or can be chosen to be, a highly composite number. The algorithm is here derived and presented in a rather different form. Attention is given to the choice of N. It is also shown how special advantage can be obtained in the use of a binary computer with N = 2' and how the entire calculation can be performed within the array of N data storage locations used for the given Fourier coefficients. Consider the problem of calculating the complex Fourier series N-1 (1) X(j) = EA(k)-Wjk, j = 0 1, * ,N- 1, k=0