FFTW

FFTW (Fastest Fourier Transform in the West) について

FFTW（Fastest Fourier Transform in the West）は、マサチューセッツ工科大学（MIT）のマテオ・フリゴとスティーブン・ジョンソンによって開発された、高速フーリエ変換（FFT）を計算するためのライブラリです。オープンソースのFFTライブラリの中でデファクトスタンダードとしての地位を確立しており、多くのUNIX系OSのパッケージ管理システムでも提供されています。

特徴

高速性: 開発者は、FFTWが2006年時点で最も高速な自由ソフトウェアのFFT実装であると主張しています。ベンチマークテストでもその速度が確認されており、実数および複素数のデータ配列をO(n log n)の計算時間で処理できます。
アルゴリズムの最適化: FFTWは、ヒューリスティックな手法を用いて、データサイズやプラットフォームに応じて最適なアルゴリズムを自動的に選択します。これにより、繰り返し同じサイズのデータに対してFFTを行う際に、常に高速な演算が期待できます。最適なアルゴリズムの選択結果はファイルに保存し、再利用することも可能です。
柔軟なインターフェース: FFTWは「guru」と呼ばれるインターフェースを備えており、これにより、メモリ上でのデータ配置を柔軟に制御できます。多次元データや複数のデータセットに対するFFTを、一度の関数呼び出しで効率的に処理できます。
並列処理: FFTWはMPI（Message Passing Interface）を用いた「非順序変換」を部分的にサポートしています。これにより、大規模なデータに対するFFT計算を、並列計算機環境で効率的に行うことが可能です。
受賞歴: FFTWは、1999年にジェームズ・H・ウィルキンソン賞を受賞しており、その技術的な貢献が認められています。

ライセンス

FFTWは、GNU General Public License v2以降、または商用ライセンスに基づいて利用および配布できます。ライセンスはGPLであるため、非商用利用の場合、FFTWを利用するソフトウェアもGPLでライセンスする必要があります。Apache Licenseなどの非GPLオープンソースソフトウェアからFFTWを直接利用することはできません。ただし、商用ライセンスを購入すれば、非GPLソフトウェアでも利用可能です。例えば、MATLABなどの商用ソフトウェアにはFFTWが組み込まれており、FFT計算の高速化に貢献しています。

APIと言語バインディング

FFTWのAPIはANSI Cで提供されており、ライブラリ自体もC言語で記述されています。また、FORTRANやC++など、他のプログラミング言語用のインターフェースも提供されています。
FFTWのコードは`genfft`というプログラムによって生成されます。このプログラムはObjective Camlで記述されています。

名称の由来

FFTWの名称にある「West（西）」は、「東洋の秘術」のようなアセンブラを使用した高度なテクニックに頼らず、最も高速なコードを目指すという開発者の姿勢を表しています。公式サイトのFAQでは、「なぜ西なのか？MITは東部にあるのでは？」という質問に対し、「開発者（フリゴ）はイタリア出身なのでそうではない」というユーモラスな回答がされています。

まとめ

FFTWは、その高速性と柔軟性から広く利用されているFFTライブラリです。しかし、GPLライセンスのため、利用には注意が必要です。特に、非GPLのソフトウェアでFFTWを利用したい場合は、商用ライセンスの購入を検討する必要があります。FFTWの利用を検討する際には、ライセンス条項をよく確認することが重要です。

関連情報

FFTPACK
フーリエ変換
離散フーリエ変換 (DFT)
* スペクトラムアナライザ

もう一度検索