Loading article…
Fastest Fourier Transform in the West ( FFTW ) は、マサチューセッツ工科大学のMatteo Frigo とSteven G. Johnsonによって開発された、離散フーリエ変換(DFT)を計算するためのソフトウェアライブラリです。[ 2 ] [ 3 ] [ 4 ]
FFTWは、高速フーリエ変換（FFT）のフリーソフトウェア実装の中でも最速クラスのものの1つです。任意のサイズと次元の実数値および複素数値配列に対してFFTアルゴリズムを実装しています。
FFTW は、さまざまなアルゴリズムをサポートし、特定の状況で好ましいと推定または測定されたアルゴリズム (変換をより小さな変換に分解した特定の方法) を選択することで、データを迅速に変換します。 FFTW は、素因数が小さいサイズの配列で最もよく機能し、2 のべき乗が最適で、大きな素数が最悪のケース (ただし、O ( n log n )) です。複合サイズの変換をより小さな変換に分解するために、Cooley–Tukey FFT アルゴリズムのいくつかのバリアント(異なる因数分解および/または異なるメモリ アクセス パターンに対応) から選択します。一方、素数サイズの場合は、RaderまたはBluestein の FFT アルゴリズムを使用します。[ 2 ]変換が十分に小さなサイズのサブ変換に分割されると、FFTW は、コード生成によって (実行時ではなくコンパイル時に)生成された、これらの小さなサイズに対するハードコードされた展開FFT を使用します。これらのルーチンは、Cooley–Tukey の変種、Rader のアルゴリズム、および素因数 FFT アルゴリズムなど、さまざまなアルゴリズムを使用します。[ 2 ]
十分な数の変換処理を繰り返す場合、指定された配列サイズとプラットフォーム上で、サポートされているアルゴリズムの一部またはすべてのパフォーマンスを測定することが有利です。著者らが「知見」と呼ぶこれらの測定結果は、後で使用するためにファイルまたは文字列に保存できます。
FFTWには、「FFTWの基盤となるアーキテクチャの柔軟性を可能な限り最大限に引き出す」ことを目的とした「エキスパートインターフェース」が備わっています。これにより、多次元変換や、単一の呼び出しで複数の変換を実行すること（例えば、データがメモリ内でインターリーブされている場合など）が可能になります。
FFTWは、順序が前後する変換（メッセージパッシングインターフェース（MPI）バージョンを使用）を限定的にサポートしています。データの順序変更にはオーバーヘッドが発生し、任意のサイズと次元のインプレース変換では、これを回避するのは容易ではありません。どの変換でこのオーバーヘッドが顕著になるかは、文書化されていません。
FFTW はGNU General Public Licenseバージョン 2 以降でライセンスされています。また、 MIT [ 5 ]による非フリー ライセンス (最大 $12,500 の費用) でも利用可能で、商用MATLAB [ 6 ]の行列パッケージで FFT の計算に使用されています。FFTW はC言語で記述されていますが、FortranおよびAda のインターフェース、その他いくつかの言語のインターフェースも存在します。ライブラリ自体は C 言語ですが、実際のコードはOCamlgenfftで記述された' ' というプログラムから生成されます。[ 7 ]
1999年、FFTWは数値計算ソフトウェア部門でJHウィルキンソン賞を受賞した。
