ベイリーのFFTアルゴリズム

16ポイントFFTのベイリーアルゴリズム（4ステップバージョン）

ベイリーのFFT （ 4ステップFFTとも呼ばれる）は、高速フーリエ変換（FFT）を計算するための高性能アルゴリズムです。このクーリー・テューキーFFTアルゴリズムの派生版は、もともと現代のコンピュータで一般的に使用されている階層型メモリを備えたシステム向けに設計されました（そして、いわゆる「アウトオブコア」クラスにおける最初のFFTアルゴリズムでした）。このアルゴリズムは、サンプルを2次元行列として扱い（そのため、行列FFTアルゴリズムとも呼ばれます^[1]）、行列の列と行に対して短いFFT演算を実行し、その間に「回転係数」による補正乗算を行います^{[2] 。}

このアルゴリズムは、 1989年に発表されたDavid H. Baileyによる論文「外部または階層的メモリ内のFFT」にちなんで名付けられました。この論文でBaileyは、このアルゴリズムを、約20年前の1966年に論文「高速フーリエ変換：楽しみと利益のために」^{[3]を発表したWM GentlemanとG. Sandeに帰しています。[4]}このアルゴリズムは、基数FFT分解と考えることができます。^[5]${\displaystyle {\sqrt {n}}}$

Bailey FFT アルゴリズムの「4 ステップ」バージョンがどのように機能するかについて、簡単に説明します。

1. まず、データ（自然な順序）がマトリックスに配列されます。
2. 次に、行列の各列は標準の FFT アルゴリズムを使用して個別に処理されます。
3. 行列の各要素には補正係数が掛けられます。
4. 次に、行列の各行は標準の FFT アルゴリズムを使用して個別に処理されます。

結果（自然順序）は列ごとに読み取られます。演算は列方向と行方向に実行されるため、ステップ2と4（および結果の読み取り）では、処理しやすいように要素を並べ替えるための行列転置が行われる場合があります。このアルゴリズムは2次元FFTに似ており、3次元（およびそれ以上）への拡張は5ステップFFT、6ステップFFTなどとして知られています。 ^{[2] [6]}

ベイリーFFTは、科学技術アプリケーションなどで使用される大規模データセットのDFT計算に典型的に用いられます。ベイリーFFTは非常に効率的なアルゴリズムであり、数十億要素のデータセットのFFT計算にも用いられてきました（数論的変換に適用した場合、 2000年代半ばには10^の12乗程度の要素を持つデータセットが処理されていました^[7]）。

参照

• 行-列FFTアルゴリズム
• ベクトル基数FFTアルゴリズム

参考文献

1. アーンドット2010、438頁。
2. ハート、トルナリア & ワトキンス 2010、p. 191.
3. Gentleman, WM; Sande, G. (1966). 「高速フーリエ変換 - 楽しみと利益のために」(PDF) . AFIPS会議論文集 第29巻. Fall Joint Computer Conference, 1966年11月7日～10日. カリフォルニア州サンフランシスコ. pp.  563– 578.
4. ベイリー 1989、2ページ。
5. Frigo & Johnson 2005、2ページ。
6. Al Na'mneh & Pan 2007、191–192 ページ。
7. アル・ナムネ＆パン 2007.

出典

• Bailey, DH (1989年3月). 「階層型メモリ外部におけるFFTS」(PDF) . 1989 ACM/IEEE スーパーコンピューティング会議論文集 - Supercomputing '89 . 第4巻. ACM Press. pp.  23– 35. doi :10.1145/76263.76288. ISBN 0897913418. S2CID  52809390。
• Frigo, M.; Johnson, SG (2005年2月). 「FFTW3の設計と実装」. Proceedings of the IEEE . 93 (2): 216– 231. Bibcode :2005IEEEP..93..216F. CiteSeerX  10.1.1.66.3097 . doi :10.1109/JPROC.2004.840301. ISSN  0018-9219. S2CID  6644892.
• ハート, ウィリアム・B.; トルナリア, ゴンサロ; ワトキンス, マーク (2010). 「1012までの合同数シータ係数」(PDF) .アルゴリズム的数論. コンピュータサイエンス講義ノート. 第6197巻. シュプリンガー・ベルリン・ハイデルベルク. pp.  186– 200. doi :10.1007/978-3-642-14518-6_17. eISSN  1611-3349. ISBN 978-3-642-14517-9. ISSN  0302-9743.
• Al Na'mneh, Rami; Pan, W. David (2007年3月). 「計算量を削減した5段階FFTアルゴリズム」. Information Processing Letters . 101 (6): 262– 267. doi :10.1016/j.ipl.2006.10.009. ISSN  0020-0190.
• アルント、イェルク（2010年10月1日）「行列フーリエアルゴリズム（MFA）」。Matters Computational：アイデア、アルゴリズム、ソースコード。Springer Science & Business Media。438  ～ 439頁。ISBN 978-3-642-14764-7. OCLC  1005788763.