FFTW
離散フーリエ変換を計算するソフトウェアライブラリー ウィキペディアから
FFTW ("Fastest Fourier Transform in the West") は離散フーリエ変換 (DFT) を計算するためのライブラリで、マサチューセッツ工科大学 (MIT) のマテオ・フリゴ (Matteo Frigo) とスティーブン・ジョンソン (Steven G. Johnson) によって開発された[2][3]。
オープンソース化されたFFTライブラリの中では、デファクトスタンダード的に用いられている。多くのUNIX系OSのパッケージ管理システムでも提供されている。ただし、ライセンスはGPLと制限が厳しく、非GPLのオープンソースソフトウェアからの利用が禁止されていて、例えばGPLではないNumPyやSciPyではFFTPACKから派生したPocketFFTを使用している[4][5]。
概要
FFTWは、2006年時点では高速フーリエ変換 (FFT) を実装した自由ソフトウェアの中ではもっとも高速である、と開発者は主張している（ベンチマークテストによる[6]）。任意のサイズの実数および複素数のデータ配列を、O(n log n) のオーダーの時間で計算することができる。
FFTWの特徴は、ヒューリスティックな方法または状況に合わせた最適な尺度で、適切なアルゴリズムを選ぶことで、高速な演算を実現していることである。他の多くの任意長データに対するFFTアルゴリズムと同様に、データ配列の長さが小さな素数の積となっているときに高速で、2のべき乗の時が最高速であり、大きな素数となっているときにもっとも遅くなるという性質がある。
同じサイズのデータのFFTを何度も繰り返しするとき、そのデータサイズと実行中のプラットフォームの種類からFFTWはもっとも適したアルゴリズムを選ぶことで、もっとも高速な演算が行える。どのアルゴリズムを選択したかをファイルに保存して、それ以降に利用することもできる。
FFTWはguruと呼ばれるインターフェイスを持ち、これにより、そのインターフェイスの後ろにあるFFTWの柔軟性をいかんなく発揮できるようにしている。これを使うとデータをメモリ上に置く順序を調整することで、多次元データや複数のデータセットのFFTを1回の関数呼び出しで行うことができる。
FFTWはMPI (Message Passing Interface) を使った「非順序変換」を部分的にサポートしている。クーリーとテューキーのFFTアルゴリズムでのデータ配置では、任意サイズのデータに対するin-place変換のときに、オーバーヘッドを避けるのは簡単なことではない。
FFTWは1999年にジェームズ・H・ウィルキンソン賞を受賞した。
ライセンス
FFTWはGNU General Public License v2 以降もしくは商用ライセンスにしたがった利用と配布ができる[1]。LGPLではなくGPLを選択しているため、商用ライセンスでない場合は、FFTWを使用しているソフトウェアもGPLでなければならない[7]。Apache Licenseなどの非GPLのオープンソースソフトウェアからは利用不可能であることに注意が必要である。FAQによるとFFTWの所有者はマサチューセッツ工科大学で、マサチューセッツ工科大学がGPL以外の採用を認めず、LGPLにすることはできなかった[8]。
マサチューセッツ工科大学から商用ライセンスを購入した場合は非GPLソフトウェアでも利用可能である。商用ソフトウェアであるMATLABにも組み込まれている[9]（つまりMATLABでFFTを計算するときにはFFTWが使われる）。
APIと言語バインディング
FFTWはANSI Cで書かれていて、APIはC言語で提供されている。FORTRANやC++など、その他の言語のインターフェイスもある。
FFTWのライブラリ自体のC言語のコードは 'genfft' というプログラムで生成されており（FFTW の配布パッケージに含まれている）、このツールはObjective Camlで書かれている[10]。
名称
名称中の「West（西、西洋）」は「東洋の秘術」（アセンブラを使ったアクロバティックなテクニックのようなもの）を使わずにもっとも高速で実行できるコードを目指していることを表わしている[11]。公式サイトのFAQでは、「西? MITは東部にあると思うけど」との質問に対して「イタリア人（開発者のフリゴはイタリア出身）にとってはそうではない」と回答されている[12]。
脚注
関連記事
Wikiwand - on
Seamless Wikipedia browsing. On steroids.