Wikipedia

FFTW

離散フーリエ変換を計算するソフトウェアライブラリー

FFTW ("Fastest Fourier Transform in the West") は離散フーリエ変換 (DFT) を計算するためのライブラリで、マサチューセッツ工科大学 (MIT) のマテオ・フリゴ (Matteo Frigo) とスティーブン・ジョンソン (Steven G. Johnson) によって開発された[1][2]。オープンソース化されたFFTライブラリの中では、デファクトスタンダード的に用いられている。多くのUNIX系OSのパッケージ管理システムでも提供されている。

FFTW
開発元 マテオ・フリゴ (Matteo Frigo)、スティーブン・ジョンソン (Steven G. Johnson)
初版 1997年3月24日 (1997-03-24)
最新版
3.3.10 / 2021年9月15日 (2年前) (2021-09-15)
リポジトリ
ウィキデータを編集
対応言語 C言語、Fortran、C++
種別 数値計算
ライセンス GPL, commercial
公式サイト www.fftw.org
テンプレートを表示

名称中の「West（西、西洋）」は「東洋の秘術」（アセンブラを使ったアクロバティックなテクニックのようなもの）を使わずにもっとも高速で実行できるコードを目指していることを表わしている[3]。公式サイトのFAQでは、「西? MITは東部にあると思うけど」との質問に対して「イタリア人（開発者のフリゴはイタリア出身）にとってはそうではない」と回答されている[4]。

FFTWは、高速フーリエ変換 (FFT) を実装したフリーソフトウェアの中ではもっとも高速である、とされている（ベンチマークテストによる[5]）。任意のサイズの実数および複素数のデータ配列を、O(n log n) のオーダーの時間で計算することができる。

FFTWの特徴は、ヒューリスティックな方法または状況に合わせた最適な尺度で、適切なアルゴリズムを選ぶことで、高速な演算を実現していることである。他の多くの任意長データに対するFFTアルゴリズムと同様に、データ配列の長さが小さな素数の積となっているときに高速で、2のべき乗の時が最高速であり、大きな素数となっているときにもっとも遅くなるという性質がある。

同じサイズのデータのFFTを何度も繰り返しするとき、そのデータサイズと実行中のプラットフォームの種類からFFTWはもっとも適したアルゴリズムを選ぶことで、もっとも高速な演算が行える。どのアルゴリズムを選択したかをファイルに保存して、それ以降に利用することもできる。

FFTWはguruと呼ばれるインターフェイスを持ち、これにより、そのインターフェイスの後ろにあるFFTWの柔軟性をいかんなく発揮できるようにしている。これを使うとデータをメモリ上に置く順序を調整することで、多次元データや複数のデータセットのFFTを1回の関数呼び出しで行うことができる。

FFTWはMPI (Message Passing Interface) を使った「非順序変換」を部分的にサポートしている。クーリーとテューキーのFFTアルゴリズムでのデータ配置では、任意サイズのデータに対するin-place変換のときに、オーバーヘッドを避けるのは簡単なことではない。

FFTWはGNU General Public Licenseにしたがった利用と配布ができる。商用ソフトウェアであるMATLABにも組み込まれている[6]（つまりMATLABでFFTを計算するときにはFFTWが使われる）。FFTWはANSI Cで書かれているが、FORTRANやC++、その他の言語のインターフェイスもある。FFTWのライブラリ自体の C言語のコードは 'genfft' というプログラムで生成されており（FFTW の配布パッケージに含まれている）、このツールはObjective Camlで書かれている[7]。

FFTWは1999年にジェームズ・H・ウィルキンソン賞を受賞した。

脚注 編集

  1. ^ 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. 
  2. ^ 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. 
  3. ^ “数値計算ライブラリ”. 地球流体電脳倶楽部. 2020年3月8日閲覧。
  4. ^ Matteo Frigo and Steven G. Johnson (2014年3月4日). “FFTW FAQ - Section 1”. 2020年3月8日閲覧。
  5. ^ FFTW ホームページの第2段落 [1] とベンチマークのページ [2]
  6. ^ “fft - ヘルプセンター”. The MathWorks, Inc.. 2020年3月8日閲覧。
  7. ^ "FFTW FAQ"

関連記事 編集

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