FFTW
FFTW ("Fastest Fourier Transform in the West") は離散フーリエ変換 (DFT) を計算するためのライブラリで、マサチューセッツ工科大学 (MIT) のマテオ・フリゴ (Matteo Frigo) とスティーブン・ジョンソン (Steven G. Johnson) によって開発された[1][2]。オープンソース化されたFFTライブラリの中では、デファクトスタンダード的に用いられている。UNIX系OSのパッケージ管理システムでも提供されている。
FFTW は、高速フーリエ変換 (FFT) を実装したフリーソフトウェアの中ではもっとも高速である、とされている (ベンチマークテストによる[3])。任意のサイズの実数および複素数のデータ配列を、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 [3] が販売しており、さらに商用ソフトウェアである MATLAB にも組み込まれている[4] (つまり MATLAB で FFT を計算するときには FFTW が使われる)。FFTW はANSI Cで書かれているが、FORTRAN や C++、その他の言語のインターフェイスもある。FFTW のライブラリ自体の C 言語のコードは 'genfft' というプログラムで生成されており (FFTW の配布パッケージに含まれている)、このツールは Objective Caml で書かれている[5]。
また FFTW は1999年に J. H. Wilkinson Prize for Numerical Software を受賞した。
脚注
- ↑ Frigo M, Johnson SG (February 2005). “The design and implementation of FFTW3”. Proceedings of the IEEE 93: 216-231. doi:10.1109/JPROC.2004.840301.
- ↑ Frigo M, Johnson SG (1998). “FFTW: an adaptive software architecture for the FFT”. Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing 3: 1381-1384. doi:10.1109/ICASSP.1998.681704.
- ↑ FFTW ホームページの第2段落 [1] とベンチマークのページ [2]
- ↑ Faster Finite Fourier Transforms: MATLAB 6 incorporates FFTW
- ↑ "FFTW FAQ"
関連記事
- FFTPACK
- フーリエ変換
- 離散フーリエ変換 (DFT)
- スペクトラムアナライザ