FFTW

FFTW
作者 マテオ・フリゴ (Matteo Frigo)、スティーブン・ジョンソン (Steven G. Johnson)
開発元 マサチューセッツ工科大学[1]
初版 1997年3月24日 (27年前) (1997-03-24)
最新版
3.3.10 / 2021年9月15日 (2年前) (2021-09-15)
リポジトリ
ウィキデータを編集
プログラミング
言語		 C言語、Fortran、C++
種別 数値計算
ライセンス GPL v2 以降、もしくは、GPL化を回避できる商用ライセンス[1]
公式サイト www.fftw.org ウィキデータを編集
テンプレートを表示

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]。

脚注[編集]

  1. ^ a b c “License and Copyright (FFTW 3.3.10)”. fftw.org. 2024年5月25日閲覧。
  2. ^ 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. http://www.fftw.org/fftw-paper-ieee.pdf. 
  3. ^ 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. http://ieeexplore.ieee.org/stamp/stamp.jsp&arnumber=681704&isnumber=14979. 
  4. ^ “numpy/numpy/fft at v1.26.5 · numpy/numpy”. 2024年5月25日閲覧。
  5. ^ “scipy/scipy/fft at v1.13.1 · scipy/scipy”. 2024年5月25日閲覧。
  6. ^ FFTW ホームページの第2段落 [1] とベンチマークのページ [2]
  7. ^ “(GPLの)及ぶ作品に対し、静的 vs 動的にリンクされたモジュールについて、GPLには異なる要求がありますか? - GNUライセンスに関してよく聞かれる質問 - GNUプロジェクト - フリーソフトウェアファウンデーション”. gnu.org. 2024年5月25日閲覧。
  8. ^ “Question 1.4. What is this about non-free licenses? - FFTW FAQ - Section 1”. fftw.org. 2024年5月25日閲覧。
  9. ^ “fft - ヘルプセンター”. The MathWorks, Inc.. 2020年3月8日閲覧。
  10. ^ "FFTW FAQ"
  11. ^ “数値計算ライブラリ”. 地球流体電脳倶楽部. 2020年3月8日閲覧。
  12. ^ Matteo Frigo and Steven G. Johnson (2014年3月4日). “FFTW FAQ - Section 1”. 2020年3月8日閲覧。

関連記事[編集]

「https://ja.wikipedia.org/w/index.php?title=FFTW&oldid=100495892」から取得