Złożoność obliczania dyskretnej transformaty Fouriera?

18

Jaka jest złożoność (na standardowej całkowitej liczbie pamięci RAM) obliczania standardowej dyskretnej transformaty Fouriera wektora n liczb całkowitych?

Klasyczny algorytm szybkich transformacji Fouriera , niewłaściwie [1] przypisany Cooleyowi i Tukeyowi, jest zwykle opisywany jako działający w czasie O(nlogn) . Ale większość operacji arytmetycznych wykonywanych w tym algorytmie rozpoczyna się od złożonych n pierwiastków jedności, które są (dla większości n ) irracjonalne, więc dokładna ocena w stałym czasie nie jest rozsądna. Ten sam problem pojawia się w przypadku naiwnego algorytmu czasu O(n2) (pomnożenie przez macierz Vandermonde'a złożonych pierwiastków jedności).

Nie jest nawet jasne, jak dokładnie reprezentować wynik DFT (w jakiejkolwiek przydatnej formie). Innymi słowy, nie jest jasne, czy obliczanie DFT jest rzeczywiście możliwe!

Więc załóżmy, musimy tylko b bitów precyzji w każdej wartości wyjściowej. Jaka jest złożoność obliczania dyskretnej transformaty Fouriera w funkcji n i b ? (Dla konkretności możesz założyć, że n jest potęgą 2 ).

Czy może każdy przypadek „FFT” w literaturze oznacza „szybką transformację teoretyczną ”? [2]

Zobacz moje powiązane pytania dotyczące złożoności eliminacji Gaussa i najkrótszych ścieżek euklidesowych .

[1] Naprawdę należy go nazwać (jakimś przedrostkiem) algorytmem Gaussa-Runge-Königa-Yatesa-Stumpfa-Danielsona-Lánczosa-Cooleya-Tukeya.

[2] A jeśli tak, to dlaczego większość podręczników opisuje tylko algorytm liczb zespolonych?

Jeffε
źródło
1
Myślę, że o to mu chodzi: teoretycznie nie musisz się martwić o , ale w każdej RZECZYWISTEJ implementacji musisz się o to martwić i popełnić błąd. b
Suresh Venkat
1
Właściwie jest to dobre pytanie, każdy dodatkowy bit precyzji dodaje do siły sygnału (pomnóż przez 2 ). Myślę więc, że pytanie będzie najbardziej przydatne, jeśli można rozszerzyć rozmiary słów pośrednich! 3dB2
vs
3
Analiza obliczeniowa rozważyła to i powiązane pytania. W pracy przedstawiono złożoność związaną z obliczeniami transformacji Fouriera w ramach skuteczności Weirauch typu II. Ograniczeniem jest to, że jest liniowy w prezentacji (nieskończonej, wartościowanej) danych wejściowych. Zarówno wejście, jak i wyjście mają zdefiniowane parametry precyzji wrt w tym systemie, więc może istnieć sposób na przełożenie tego na model pamięci RAM.
Aaron Sterling
3
Spójrz na Metodę A w artykule Schönhage'a i Strassena na temat mnożenia liczb całkowitych. Wykorzystuje złożone transformaty Fouriera z ograniczoną precyzją. Myślę, że jest to również opisane w Knuth Vol. 2.
Markus Bläser
2
Markus, Aaron: konwertować na odpowiedzi?
Suresh Venkat,

Odpowiedzi:

9

Ta odpowiedź jest wariantem analizy pierwszego algorytmu („Methode A”) Schönhage'a i Strassena do mnożenia długich liczb całkowitych.

Załóżmy, że chcemy obliczyć FFT o długości . Skaluj dane wejściowe tak, aby wszystkie wartości były mniejsze niż 1. Załóżmy najpierw, że obliczamy z arytmetyką stałego punktu m -bit ( m bitów po punkcie binarnym). Niech δ = 2 1 / 2 - m jest ( "kompleks"), jednostka najmniej położeniu. Niech ω = exp ( 2 π i / K ) .K=2kmmδ=21/2mω=exp(2πi/K)

1) Można obliczyć przybliżenia takie, że | ω j - ω j | ( 2 k - 1 ) δ dla wszystkich 0 j K - 1 . Można tego dokonać w czasie O ( K M ( m ) ), gdzie M ( m ) to czas potrzebny do pomnożenia liczby m- bitowej. (patrz Knuth Vol. 2, wydanie trzecie, strona 309).ωj|ωjωj|(2k1)δ0jK1O(KM(m))M(m)m

Jeśli standardowa liczba całkowita RAM oznacza koszt logarytmiczny, to . Jeśli standardowa liczba całkowita RAM oznacza słowo RAM, to M ( m ) = O ( m ) . (Schönhage i Strassen pokazują w „Metodzie A”, jak zmniejszyć w czasie liniowym mnożenie liczb m- bitowych do m mnożenia liczb bitów O ( log m ) . To ostatnie można zrobić po kosztach jednostkowych.)M(m)=O(mlogm)M(m)=O(m)mmO(logm)

2) Klasyczna metoda FFT Cooleya-Tukeya oblicza operacje w postaci . Stosujemy arytmetykę stałoprzecinkową m- bit, te opcje stają się a = t r u n c a t e ( b + ω j c ) . Jeśli wiemya=b+ωjcma=truncate(b+ωjc) i C ' aż do błędu ε , dostajemy ' do błędu 2 ε + 2bcϵa .2ϵ+2kδ

3) Za pomocą indukcji łatwo zauważyć, że otrzymujemy końcowy wynik z błędem (2k1)2kδ . Aby uzyskać precyzję na końcu, m k + log k + b + O ( 1 ) . bmk+logk+b+O(1)

4) Zatem końcowy czas pracy wynosi .O(KkM(k+b))

Powinno to również działać z liczbami zmiennoprzecinkowymi: 1) nadal można to zrobić za pomocą arytmetyki stałych punktów, 2) jest również prawdziwe w przypadku liczb zmiennoprzecinkowych.


Wydaje mi się, że w arytmetyki punktu stałego można to zrobić nawet szybciej. Najpierw redukujemy obliczenia FFT do mnożenia wielomianów za pomocą sztuczki Bluesteina. Długość współczynników potrzebnych do uzyskania pożądanej precyzji powinna wynosić . Następnie zmniejszamy mnożenie wielomianów do mnożenia długich liczb całkowitych. (Dołącz współczynniki do długiej liczby i rozdziel je blokami zerowymi o długości O ( k + b ) .) Długość liczb całkowitych wynosi O ( K ( k + b ) ) .O(k+b)O(k+b)O(K(k+b))

Markus Bläser
źródło
Więc od punktu (4), ustawiając K = nib = O (log n) i zakładając, że działamy na słowie RAM, otrzymujemy czas działania . Dobrze? O(nlog2n)
Jeffε
Tak. Drugi algorytm daje nawet , zakładając, że dokładność O ( k + b ) jest wystarczająca. (Nie widzę sensu, dlaczego to nie wystarczy, ale nie O(nlogn)O(k+b)
podałem
2
BTW, jeśli jest tak małe jak O ( log n ) , to również pierwszy algorytm podaje czas działania O ( n log n ), ponieważ M ( O ( log n ) ) = 1 . bO(logn)O(nlogn)M(O(logn))=1
Markus Bläser,
Zdarzyło mi się spojrzeć na książkę Aho, Hopcrofta i Ullmana na temat „Projektowanie i analiza algorytmów”, a oni szczegółowo omawiają algorytm w modelu bitowym i związane z tym zagadnienia.
Chandra Chekuri,
Ale o ile pamiętam, dyskutują tylko o „teorii liczb FFT” w modelu bitowym.
Markus Bläser,
8

To nie jest pełna odpowiedź, ale mogę wskazać kilka istotnych artykułów, a także częściowo wyjaśnić, dlaczego nie jest tak łatwo wydobyć odpowiedź z konkretnego pytania z literatury.

Zacznę od pytania, dlaczego chcesz poznać odpowiedź na to pytanie? Zazwyczaj ludzie, którym zależy na tego rodzaju problemach, to ci, którzy faktycznie muszą wdrożyć wysokowydajny FFT do praktycznego zastosowania. Tacy ludzie mniej troszczą się o asymptotyczną złożoność w wyidealizowanym modelu obliczeniowym niż o maksymalizację wydajności przy określonych ograniczeniach sprzętowych i programowych. Na przykład twórcy najszybszej transformacji Fouriera na Zachodzie piszą w swoim artykule:

Najlepszy wybór zależy od szczegółów sprzętowych, takich jak liczba rejestrów, opóźnienie i przepustowość instrukcji, rozmiar i powiązanie pamięci podręcznych, struktura potoku procesora itp.

Są to problemy, z którymi teoretycy zazwyczaj nie chcą się zmrużyć, ale mają ogromne znaczenie w rzeczywistych implementacjach. Jeśli teoretyk oświadczy: „Odkryłem absolutnie najlepszą asymptotyczną złożoność bitów w modelu RAM”, praktykujący może powiedzieć: „To miłe”, ale może uznać taki teoretyczny wynik za bezużyteczny dla swoich celów.

Powiedziawszy to, uważam, że najlepiej jest spojrzeć na literaturę analityczną. Na przykład, Tasche i Zeuner dokładnie przyjrzeli się stabilności liczbowej algorytmu FFT. To może wciąż nie być dokładnie to, czego chcesz, ponieważ ogólny konsensus wśród praktyków wydaje się, że aby osiągnąć określoną liczbę liczbową precyzję, najlepszym praktycznym podejściem jest wstępne obliczenie pewnych liczb zwanych „współczynnikami zmienności” z wysoką dokładnością. Jeśli wykonujesz tylko jedną FFT, nie będzie to najszybsze podejście, ponieważ nie będziesz w stanie amortyzować kosztu jednorazowego wstępnego obliczenia w stosunku do dużej liczby obliczeń FFT. Mimo to ich analiza najgorszego przypadku błędu zaokrąglenia powinna być nadal odpowiednia dla twojego pytania.

Timothy Chow
źródło
11024100
1
Interesuje mnie pytanie czysto teoretyczne, w interesie prawidłowego i uczciwego stypendium. Często czytane jest „i tutaj używamy FFT, który jak wszyscy wiemy działa w czasie O (n log n)” w środku skądinąd czysto kombinatorycznego algorytmu, inaczej analizowanego pod kątem przechodzenia wskaźnika i O (log n ) -bitowa arytmetyka liczb całkowitych. Jeśli w rzeczywistości splot całkowity może być przeprowadzony w czasie O (n log n) przy użyciu niewielkiego wariantu FFT, jest to być może wybaczalne, ale wciąż niechlujne. Jeśli nie, każdy biedny schmuck, który próbuje zaimplementować algorytm, otrzyma NIEPRAWIDŁOWĄ ODPOWIEDŹ.
Jeffε
I oczywiście nie oczekuję, aby odpowiedź na moje pytanie miała jakikolwiek wpływ w praktyce.
Jeffε
2
Jeff, jeśli chodzi o uczciwe stypendium, czy nie wystarczy powiedzieć, że FFT wymaga operacji O (n log n)? Jest to naturalny sposób pomiaru złożoności algorytmu FFT. Nie widzę motywacji do przekształcenia wszystkiego w jeden konkretny model obliczeń. Czy istnieje jakieś twierdzenie, które próbujesz udowodnić, gdzie kluczowe jest śledzenie liczby bitów precyzji? Co do twojego biednego szmucka, nie kupuję, że dostanie „złą odpowiedź”. W jakiejkolwiek rzeczywistej realizacji pytanie, które tu zadajesz, raczej nie będzie dominującym problemem.
Timothy Chow,
O(nlogn)