FFTW - FFTW
tento článek se mohou příliš spoléhat na zdroje příliš úzce souvisí s tématem, což potenciálně brání tomu, aby článek byl ověřitelný a neutrální.Dubna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Logo FFTW | |
Vývojáři | Matteo Frigo a Steven G. Johnson |
---|---|
První vydání | 24. března 1997 |
Stabilní uvolnění | 3.3.8 / 28. května 2018 |
Úložiště | |
Napsáno | C, OCaml |
Typ | Numerický software |
Licence | GPL, komerční |
webová stránka | www |
The Nejrychlejší Fourierova transformace na Západě (FFTW) je software knihovna pro výpočet diskrétní Fourierovy transformace (DFT) vyvinuté Matteo Frigo a Steven G. Johnson na Massachusetts Institute of Technology.[1][2][3]
FFTW je známý jako nejrychlejší svobodný software provádění rychlá Fourierova transformace (FFT) (potvrzeno pravidelným měřítka[4]). Stejně jako mnoho jiných implementací dokáže vypočítat transformace skutečných a komplex - hodnotná pole libovolné velikosti a dimenze v Ó (n logn ) čas.
Knihovna
Dělá to podporou různých algoritmů a výběrem toho (konkrétního rozkladu transformace na menší transformace) odhady nebo opatření, která jsou za konkrétních okolností výhodnější. Funguje nejlépe na polích velikostí s malými hlavní faktory, s pravomoci dvou být optimální a velký připraví je nejhorší případ (ale přesto Ó (n log n )). Rozložit transformace kompozitní velikosti do menších transformací, vybírá si mezi několika variantami Algoritmus FFT Cooley – Tukey (odpovídá různým faktorizacím a / nebo různým vzorům přístupu do paměti), zatímco pro hlavní velikosti používá buď Rader nebo Bluesteinův FFT algoritmus.[1] Jakmile je transformace rozdělena na subtransformace dostatečně malých velikostí, používá FFTW napevno rozvinutý FFT pro tyto malé velikosti, které byly vyrobeny (v čas kompilace, ne v doba běhu ) od generování kódu; tyto rutiny používají různé algoritmy včetně variant Cooley – Tukey, Raderův algoritmus a algoritmy FFT prime-factor.[1]
Pro dostatečně velký počet opakovaných transformací je výhodné měřit výkon některých nebo všech podporovaných algoritmů na dané velikosti pole a plošina. Tato měření, která autoři označují jako „moudrost“, lze uložit do souboru nebo řetězce pro pozdější použití.
FFTW má „guru rozhraní“, které má v úmyslu „vystavit co nejvíce flexibility v základní architektuře FFTW“. To umožňuje mimo jiné vícerozměrné transformace a více transformací v jednom volání (např. Tam, kde jsou data prokládána v paměti).
FFTW má omezenou podporu pro out-of-order transformace (za použití Rozhraní pro předávání zpráv (MPI) verze). The přeskupování dat způsobí režii, která je pro místní transformace libovolné velikosti a dimenze netriviální, aby se zabránilo. Je nezdokumentováno, pro které je transformace této režie významná.
FFTW je licencován pod GNU General Public License. Je také komerčně licencován (za cenu až 12 500 $) společností MIT[5] a používá se v reklamě MATLAB[6] maticový balíček pro výpočet FFT. FFTW je napsán v C jazyk, ale Fortran a Ada existují rozhraní i rozhraní pro několik dalších jazyků. Zatímco samotná knihovna je C, kód je ve skutečnosti generován z programu s názvem 'genfft
', který je napsán v OCaml.[7]
V roce 1999 FFTW vyhrál Cena J. H. Wilkinsona za numerický software.
Viz také
Reference
- ^ A b C Frigo M, Johnson SG (únor 2005). „Návrh a implementace FFTW3“ (PDF). Sborník IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109 / JPROC.2004.840301.
- ^ Frigo M, Johnson SG (1998). FFTW: adaptivní softwarová architektura pro FFT. Sborník mezinárodní konference IEEE z roku 1998 o akustice, řeči a zpracování signálu. 3. str. 1381–1384. CiteSeerX 10.1.1.47.8661. doi:10.1109 / ICASSP.1998.681704. ISBN 978-0-7803-4428-0.
- ^ Johnson SG, Frigo M (září 2008). "ch.11: Implementace FFT v praxi". V publikaci C. S. Burrus (ed.). Rychlé Fourierovy transformace. Houston TX: Connexions: Rice University.
- ^ Domovská stránka, druhý odstavec [1] a stránky s referenčními hodnotami [2]
- ^ "Zobrazit technologie | MIT Technology Licensing Office".
- ^ Rychlejší konečné Fourierovy transformace: MATLAB 6 obsahuje FFTW
- ^ „FFTW FAQ“