メインメニューを開く

FFTW ("Fastest Fourier Transform in the West") は離散フーリエ変換 (DFT) を計算するためのライブラリで、マサチューセッツ工科大学 (MIT) のマテオ・フリゴ (Matteo Frigo) とスティーブン・ジョンソン (Steven G. Johnson) によって開発された[1][2]オープンソース化されたFFTライブラリの中では、デファクトスタンダード的に用いられている。UNIX系OSパッケージ管理システムでも提供されている。

FFTW
開発元 マテオ・フリゴ (Matteo Frigo)、スティーブン・ジョンソン (Steven G. Johnson)
初版 1997年3月24日 (1997-03-24)
最新版 3.3.8 / 2018年5月28日(16か月前) (2018-05-28
リポジトリ github.com/FFTW/fftw3
対応言語 C言語FortranC++
種別 数値計算
ライセンス GPL, commercial
公式サイト www.fftw.org
テンプレートを表示

FFTW は、高速フーリエ変換 (FFT) を実装したフリーソフトウェアの中ではもっとも高速である、とされている (ベンチマークテストによる[3])。任意のサイズの実数および複素数のデータ配列を、O(n log n) のオーダーの時間で計算することができる。

FFTW の特徴は、ヒューリスティックな方法または状況に合わせた最適な尺度で、適切なアルゴリズムを選ぶことで、高速な演算を実現していることである。他の多くの任意長データに対する FFT アルゴリズムと同様に、データ配列の長さが小さな素数の積となっているときに高速で、2のべき乗の時が最高速であり、大きな素数となっているときにもっとも遅くなるという性質がある。

同じサイズのデータの FFT を何度も繰り返しするとき、そのデータサイズと実行中のプラットフォームの種類からFFTW はもっとも適したアルゴリズムを選ぶことで、もっとも高速な演算が行える。どのアルゴリズムを選択したかをファイルに保存して、それ以降に利用することもできる。

FFTW は guru と呼ばれるインターフェイスを持ち、これにより、そのインターフェイスの後ろにある FFTW の柔軟性をいかんなく発揮できるようにしている。これを使うとデータをメモリ上に置く順序を調整することで、多次元データや複数のデータセットの FFT を1回の関数呼び出しで行うことができる。

FFTW は MPI (Message Passing Interface) を使った「非順序変換」を部分的にサポートしている。クーリーとテューキーの FFT アルゴリズムでのデータ配置では、任意サイズのデータに対する in-place 変換のときに、オーバーヘッドを避けるのは簡単なことではない。

FFTW は GNU General Public License にしたがった利用と配布ができる。また、MIT [3] が販売しており、さらに商用ソフトウェアである MATLAB にも組み込まれている[4] (つまり MATLAB で FFT を計算するときには FFTW が使われる)。FFTW はANSI Cで書かれているが、FORTRANC++、その他の言語のインターフェイスもある。FFTW のライブラリ自体の C 言語のコードは 'genfft' というプログラムで生成されており (FFTW の配布パッケージに含まれている)、このツールは Objective Caml で書かれている[5]

また FFTW は1999年に J. H. Wilkinson Prize for Numerical Software を受賞した。

脚注編集

関連記事編集