FFTW
FFTW ("Fastest Fourier Transform in the West") は離散フーリエ変換 (DFT) を計算するためのライブラリで、マサチューセッツ工科大学 (MIT) のマテオ・フリゴ (Matteo Frigo) とスティーブン・ジョンソン (Steven G. Johnson) によって開発された。オープンソース化されたFFTライブラリの中では、デファクトスタンダード的に用いられている。多くのUNIX系OSのパッケージ管理システムでも提供されている。
名称中の「West(西、西洋)」は「東洋の秘術」(アセンブラを使ったアクロバティックなテクニックのようなもの)を使わずにもっとも高速で実行できるコードを目指していることを表わしている。公式サイトのFAQでは、「西? MITは東部にあると思うけど」との質問に対して「イタリア人(開発者のフリゴはイタリア出身)にとってはそうではない」と回答されている。
FFTWは、高速フーリエ変換 (FFT) を実装したフリーソフトウェアの中ではもっとも高速である、とされている(ベンチマークテストによる)。任意のサイズの実数および複素数のデータ配列を、O(n log n) のオーダーの時間で計算することができる。
FFTWの特徴は、ヒューリスティックな方法または状況に合わせた最適な尺度で、適切なアルゴリズムを選ぶことで、高速な演算を実現していることである。他の多くの任意長データに対するFFTアルゴリズムと同様に、データ配列の長さが小さな素数の積となっているときに高速で、2のべき乗の時が最高速であり、大きな素数となっているときにもっとも遅くなるという性質がある。