(Translated by https://www.hiragana.jp/)
FFTW - Wikipedia コンテンツにスキップ

FFTW

出典しゅってん: フリー百科ひゃっか事典じてん『ウィキペディア（Wikipedia）』

2024年ねん5月がつ25日にち (土)ど 20:16; C8uyPqgR (会話かいわ | 投稿とうこう記録きろく) による版はん（日時にちじは個人こじん設定せっていで未み設定せっていならUTC）

(差分さぶん) ← 古ふるい版はん | 最新さいしん版ばん (差分さぶん) | 新あたらしい版はん → (差分さぶん)
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」から取得しゅとく