|
FFTW ("Fastest Fourier Transform in the West") は離散フーリエ変換 (DFT) を計算するためのライブラリで、マサチューセッツ工科大学 (MIT) のマテオ・フリゴ (Matteo Frigo) とスティーブン・ジョンソン (Steven G. Johnson) によって開発された。 FFTW は、高速フーリエ変換 (FFT) を実装したフリーソフトウェアの中ではもっとも高速である、とされている (ベンチマークテストによる〔FFTW ホームページの第2段落 とベンチマークのページ 〕)。任意のサイズの実数および複素数のデータ配列を、O(n log n) のオーダーの時間で計算することができる。 FFTW の特徴は、ヒューリスティックな方法または状況に合わせた最適な尺度で、適切なアルゴリズムを選ぶことで、高速な演算を実現していることである。他の多くの任意長データに対する FFT アルゴリズムと同様に、データ配列の長さが小さな素数の積となっているときに高速で、２のべき乗の時が最高速であり、大きな素数となっているときにもっとも遅くなるという性質がある。 同じサイズのデータの FFT を何度も繰り返しするとき、そのデータサイズと実行中のプラットフォームの種類からFFTW はもっとも適したアルゴリズムを選ぶことで、もっとも高速な演算が行える。どのアルゴリズムを選択したかをファイルに保存して、それ以降に利用することもできる。 FFTW は guru と呼ばれるインターフェイスを持ち、これにより、そのインターフェイスの後ろにある FFTW の柔軟性をいかんなく発揮できるようにしている。これを使うとデータをメモリ上に置く順序を調整することで、多次元データや複数のデータセットの FFT を1回の関数呼び出しで行うことができる。 FFTW は MPI (Message Passing Interface) を使った「非順序変換」を部分的にサポートしている。クーリーとテューキーの FFT アルゴリズムでのデータ配置では、任意サイズのデータに対する in-place 変換のときに、オーバーヘッドを避けるのは簡単なことではない。 FFTW は GNU General Public License にしたがった利用と配布ができる。また、MIT が販売しており、さらに商用ソフトウェアである MATLAB にも組み込まれている〔Faster Finite Fourier Transforms: MATLAB 6 incorporates FFTW 〕 (つまり MATLAB で FFT を計算するときには FFTW が使われる)。FFTW はANSI Cで書かれているが、FORTRAN や C++、その他の言語のインターフェイスもある。FFTW のライブラリ自体の C 言語のコードは ' genfft' というプログラムで生成されており (FFTW の配布パッケージに含まれている)、このツールは Objective Caml で書かれている〔"FFTW FAQ" 〕。また FFTW は1999年に J. H. Wilkinson Prize for Numerical Software を受賞した。 == 脚注 == 〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「FFTW」の詳細全文を読む スポンサード リンク
|