An Algorithm for the Machine Calculation of Complex Fourier Series

複素フーリエ級数の機械計算のためのアルゴリズム

James W. Cooley and John W. Tukey による

$2^m$要因実験の交互作用を計算する効率的な方法はYatesによって導入され、広く彼の名で知られている。$3^m$への一般化はBox et al. [1]によって与えられた。Good [2]はこれらの方法を一般化し、その応用の一分野としてフーリエ級数の計算に用いることのできる優れたアルゴリズムを与えた。Goodの方法はその最も一般的な形では、$N$-ベクトルに、$m$個の疎行列に因数分解できる$N \times N$行列を乗算しなければならないある種の問題に適用できる。ただし、$m$は$\log N$に比例する。この結果、$N^2$ではなく$N \log N$に比例する数の演算を必要とする手続きが得られる。ここではこれらの方法を複素フーリエ級数の計算に適用する。これはデータ点の数が非常に合成数である場合、またはそのように選択できる場合に有用である。ここではアルゴリズムをかなり異なる形で導出し、提示する。$N$の選択についても考察する。また、$N = 2^m$とした二進コンピューターを使用することで特別な利点が得られること、および与えられたフーリエ係数に用いる$N$個のデータ記憶場所からなる配列内だけで計算全体を実行できることを示す。

複素フーリエ級数を計算する問題を考える。