FFTW - FFTW

FFTW
Logo FFTW
Logo FFTW
Vývojáři Matteo Frigo a Steven G. Johnson
První vydání 24. března 1997  ( 1997-03-24 )
Stabilní uvolnění
3.3.9 / 13. prosince 2020 ; Před 55 dny  ( 2020-12-13 )
Úložiště Upravte to na Wikidata
Napsáno C , OCaml
Typ Numerický software
Licence GPL , komerční
webová stránka www .fftw .org  Upravte to na Wikidata

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 .

Viz také

Reference

externí odkazy