FFT omija ogromną część pracy, wykorzystując symetrię pierwiastków z jedności
Bezpośrednie obliczenie dyskretnej transformaty Fouriera dla N punktów wymaga w prostym ujęciu około N wyników, z których każdy sumuje wkład N próbek — pracy rzędu N². Szybka transformata Fouriera nie zmienia samej transformaty; zmienia sposób jej obliczania. Algorytm Cooleya–Tukeya rozkłada problem na mniejsze transformaty, wykorzystując powtarzające się i symetryczne potęgi zespolonych pierwiastków z jedności. Dla typowych rozmiarów prowadzi to do kosztu rzędu N log N. Różnica jest tak duża, że FFT stała się podstawowym narzędziem przetwarzania sygnałów, obrazów, konwolucji i wielu szybkich metod arytmetycznych.
Ta sama transformata, mniej powtarzanej pracy
Dyskretna transformata Fouriera przekształca N próbek w N współczynników opisujących składowe częstotliwościowe. Z definicji każdy współczynnik jest sumą N wyrazów z odpowiednimi zespolonymi mnożnikami. Jeśli obliczymy każdy wynik niezależnie, dostajemy około N·N operacji podstawowych. Przy N=milion taki naiwny schemat sugeruje skalę biliona par wkładów.
FFT nie jest innym przybliżeniem DFT. Przy tej samej arytmetyce oblicza ten sam wynik, lecz reorganizuje działania. Klucz polega na tym, że wiele współczynników używa tych samych potęg pierwiastków z jedności, a te mają regularną strukturę. Wartości pośrednie można więc współdzielić zamiast obliczać ponownie.
Parzyste i nieparzyste próbki tworzą mniejsze problemy
W klasycznym wariancie radix-2 dzielimy sumę na wkład indeksów parzystych i nieparzystych. Każda część okazuje się transformatą o połowę mniejszą. Następnie wyniki dwóch mniejszych DFT łączy się za pomocą odpowiednich „twiddle factors”. Ten podział można powtarzać rekurencyjnie, aż pozostaną bardzo małe przypadki.
Zamiast N poziomów pracy po N elementów otrzymujemy około log2 N poziomów, z których każdy wymaga pracy liniowej. Stąd O(N log N). Oryginalna praca Jamesa Cooleya i Johna Tukeya z 1965 roku przedstawiła algorytm efektywnego maszynowego obliczania zespolonych szeregów Fouriera i stała się jednym z najbardziej wpływowych opisów FFT. Istnieje wiele odmian dla innych rozkładów N oraz innych warunków.
Przyspieszenie zmienia to, co w ogóle da się robić
Różnica między N² a N log N nie jest subtelną optymalizacją. Dla N=1 048 576, czyli 2^20, czynnik log2 N wynosi 20. Modelowa liczba jednostek pracy N log2 N jest więc rzędu 21 milionów, podczas gdy N² przekracza bilion. Rzeczywiste implementacje mają stałe, pamięć, wektoryzację i wiele innych kosztów, więc nie wolno traktować tych liczb jak dokładnego czasu procesora. Pokazują jednak skalę asymptotycznej różnicy.
Dzięki temu analiza częstotliwościowa dużych sygnałów może być wykonywana rutynowo. Szybkie konwolucje wykorzystują fakt, że splot w jednej dziedzinie odpowiada mnożeniu w drugiej. FFT stała się więc nie tylko algorytmem „od dźwięku”, lecz narzędziem do reorganizowania wielu rodzajów obliczeń.
Ta idea wraca nawet przy mnożeniu wielkich liczb
Duże liczby można traktować jak ciągi cyfr lub bloków, a ich mnożenie ma związek z konwolucją takich ciągów. To otwiera drogę do metod opartych na transformacjach. Dokumentacja GNU MP pokazuje wielowarstwowy wybór algorytmów: dla małych operandów baza, później Karatsuba i Toom, a dla wystarczająco dużych danych także mnożenie FFT.
To dobry przykład ewolucji algorytmicznej. FFT nie „przyspiesza procesora”; odsłania strukturę algebraiczną, która wcześniej była marnowana przez powtarzanie podobnych sum. Kiedy raz znajdzie się taki sposób faktoryzacji obliczenia, jego wpływ może przejść daleko poza problem, dla którego użytkownik pierwszy raz spotkał transformację Fouriera.
Odwrotna transformata pozwala wrócić z wyniku do danych
FFT jest algorytmem szybkiego obliczania transformacji, ale równie ważna jest transformata odwrotna. Po wykonaniu operacji wygodnych w dziedzinie częstotliwości — na przykład mnożenia współczynników odpowiadającego konwolucji — można wrócić do reprezentacji czasowej lub współczynników wielomianu. W klasycznych konstrukcjach szybka transformata odwrotna ma tę samą asymptotyczną złożoność O(N log N). Dzięki temu cały schemat „przekształć → wykonaj prostszą operację → odwróć przekształcenie” pozostaje efektywny. To właśnie ta możliwość czyni FFT narzędziem do przyspieszania nie tylko analizy widma, ale całych klas obliczeń.
Konwolucja zamienia się po transformacji w prostsze mnożenie punkt po punkcie
Jednym z powodów ogromnego znaczenia FFT jest twierdzenie o konwolucji. Bezpośrednie policzenie splotu dwóch ciągów długości N ma naiwnie koszt kwadratowy, ponieważ każdy element jednej sekwencji oddziałuje z wieloma elementami drugiej. Można jednak przetransformować oba ciągi, pomnożyć odpowiadające sobie współczynniki i wykonać transformację odwrotną. Dwie szybkie transformacje, jedno mnożenie punktowe i szybki powrót prowadzą do kosztu rzędu N log N zamiast N² dla dużych problemów. Ten sam schemat stoi za powiązaniem FFT z mnożeniem wielomianów i wielkich liczb. Najważniejsza sztuczka nie polega więc wyłącznie na szybszym policzeniu widma, lecz na przeniesieniu trudnej operacji do reprezentacji, w której staje się algebraicznie prostsza.