「FFTW」の版間の差分

2022年11月13日 (日) 23:23時点における版

2023年9月26日 (火) 07:06時点における版

20行目:

'''FFTW''' ("'''Fastest Fourier Transform in the West'''") は[[離散フーリエ変換]] (DFT) を計算するための[[ライブラリ]]で、[[マサチューセッツ工科大学]] (MIT) のマテオ・フリゴ (Matteo Frigo) とスティーブン・ジョンソン (Steven G. Johnson) によって開発された<ref name="Frigo2005">{{cite journal |author=Frigo M, Johnson SG |url=http://www.fftw.org/fftw-paper-ieee.pdf |title=The design and implementation of FFTW3 |journal=Proceedings of the IEEE |volume=93 |issue2 |month=February |year=2005 |page=216-231 |doi=10.1109/JPROC.2004.840301}}</ref><ref name="Frigo1998">{{cite journal |author=Frigo M, Johnson SG |title=FFTW: an adaptive software architecture for the FFT |journal=Proceedings of the 1998 IEEE [[International Conference on Acoustics, Speech and Signal Processing]] |volume=3 |page=1381-1384 |year=1998 |url=http://ieeexplore.ieee.org/stamp/stamp.jsp&arnumber=681704&isnumber=14979 |doi=10.1109/ICASSP.1998.681704}}</ref>。[[オープンソース]]化された[[FFT]]ライブラリの中では、[[デファクトスタンダード]]的に用いられている。多くの[[Unix系|UNIX系OS]]の[[パッケージ管理システム]]でも提供されている。

名称中の「West（西、西洋）」は「東洋の秘術」（[[アセンブラ]]を使ったアクロバティックなテクニックのようなもの）を使わずにもっとも高速で実行できるコードを目指していることを表わしている<ref>{{citeCite web|和書|url=http://www.gfd-dennou.org/member/murashin/memo/num-comp-library.html|title=数値計算ライブラリ|publisher=地球流体電脳倶楽部|accessdate=2020-03-08}}</ref>。公式サイトの[[FAQ]]では、「西? MITは東部にあると思うけど」との質問に対して「イタリア人（開発者のフリゴはイタリア出身）にとってはそうではない」と回答されている<ref>{{cite web|url=http://www.fftw.org/faq/section1.html#west|title= FFTW FAQ - Section 1|author=Matteo Frigo and Steven G. Johnson |date=2014-03-04|accessdate=2020-03-08}}</ref>。

FFTWは、[[高速フーリエ変換]] (FFT) を実装した[[フリーソフトウェア]]の中ではもっとも高速である、とされている（ベンチマークテストによる<ref>FFTW ホームページの第2段落 [http://www.fftw.org/] とベンチマークのページ [http://www.fftw.org/benchfft/]</ref>）。任意のサイズの実数および複素数のデータ配列を、[[ランダウの記号|O]](n log n) のオーダーの時間で計算することができる。

32行目:

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

FFTWは[[GNU General Public License]]にしたがった利用と配布ができる。商用ソフトウェアである[[MATLAB]]にも組み込まれている<ref>{{citeCite web|和書|url=https://jp.mathworks.com/help/matlab/ref/fft.html|title= fft - ヘルプセンター|publisher=The MathWorks, Inc.|accessdate=2020-03-08}}</ref>（つまりMATLABでFFTを計算するときにはFFTWが使われる）。FFTWは[[C言語|ANSI C]]で書かれているが、[[FORTRAN]]や[[C++]]、その他の言語のインターフェイスもある。FFTWのライブラリ自体の C言語のコードは '<code>genfft</code>' というプログラムで生成されており（FFTW の配布パッケージに含まれている）、このツールは[[Objective Caml]]で書かれている<ref name="FFTW FAQ">[http://www.fftw.org/faq/section2.html#languages "FFTW FAQ"]</ref>。

FFTWは1999年に[[J. H. Wilkinson Prize for Numerical Software]]を受賞した。