FFTW - FFTW
Logo FFTW
| |
Vývojáři | Matteo Frigo a Steven G. Johnson |
---|---|
První vydání | 24. března 1997 |
Stabilní uvolnění | 3.3.9 / 13. prosince 2020
|
Úložiště | |
Napsáno | C , OCaml |
Typ | Numerický software |
Licence | GPL , komerční |
webová stránka |
www |
Nejrychlejší Fourierova transformace na Západě ( FFTW ) je softwarová knihovna pro výpočet diskrétní Fourierova transformace (DFT), kterou vypracovala Matteo Frigo a Steven G. Johnson na Massachusetts Institute of Technology .
FFTW je známý jako nejrychlejší bezplatná softwarová implementace rychlé Fourierovy transformace (FFT) (potvrzená pravidelnými měřítky ). Stejně jako mnoho jiných implementací může vypočítat transformace reálných a komplexních polí libovolné velikosti a dimenze v čase O ( n log n ).
Knihovna
FFTW rychle transformuje data podporou různých algoritmů a výběrem toho (konkrétního rozkladu transformace na menší transformace), který za konkrétních okolností odhaduje nebo měří jako výhodnějšího. Funguje nejlépe na polích velikostí s malými prvočísly , přičemž síly dvou jsou optimální a velké prvočísla jsou nejhorší případ (ale stále O ( n log n )). K rozložení transformací složených velikostí na menší transformace si vybere z několika variant algoritmu Cooley – Tukey FFT (odpovídajících různým faktorizacím a / nebo různým vzorům přístupu do paměti), zatímco pro primární velikosti používá buď FFT algoritmus Radera, nebo Bluesteina . Jakmile byla transformace rozdělena na subtransformace dostatečně malých velikostí, používá FFTW pevně kódované rozvinuté FFT pro tyto malé velikosti, které byly vytvořeny (v době kompilace , ne za běhu ) generováním kódu ; tyto rutiny používají různé algoritmy včetně variant Cooley – Tukey, Raderův algoritmus a FFT algoritmy prime-factor .
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 platformě . 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 transformace mimo pořadí (pomocí verze rozhraní pro předávání zpráv (MPI)). Změna pořadí dat má za následek režii, která pro místní transformace libovolné velikosti a dimenze není triviální, aby se zabránilo. Je nezdokumentováno, pro které je transformace této režie významná.
FFTW je licencován na základě GNU General Public License . Je také komerčně licencován (za cenu až 12 500 USD) společností MIT a používá se v komerčním maticovém balíčku MATLAB pro výpočet FFT. FFTW je napsán v jazyce C , ale existují rozhraní Fortran a Ada , stejně jako 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 .
V roce 1999 FFTW získal cenu JH Wilkinsona za numerický software .