Komplexität der Berechnung der diskreten Fouriertransformation?

Wie komplex ist die Berechnung der diskreten Fourier- Standardtransformation eines Vektors von ganzen Zahlen (im Standard-Ganzzahl-RAM) ?$n$

Der klassische Algorithmus für schnelle Fourier-Transformationen ^[1] , der Cooley und Tukey unangemessen zugeschrieben wird, wird normalerweise als in -Zeit laufend beschrieben . Die meisten in diesem Algorithmus ausgeführten arithmetischen Operationen beginnen jedoch mit komplexen n- ten Wurzeln der Einheit, die (für die meisten n ) irrational sind, so dass eine genaue Auswertung in konstanter Zeit nicht sinnvoll ist. Das gleiche Problem tritt beim naiven O ( n 2 ) -Zeitalgorithmus auf (Multiplikation mit einer Vandermonde-Matrix komplexer Einheitswurzeln).$O(n \log n)$$n$$n$$O(n^2)$

Es ist nicht einmal klar, wie die Ausgabe der DFT genau dargestellt werden soll (in irgendeiner nützlichen Form). Mit anderen Worten, es ist nicht klar, dass die Berechnung von DFTs tatsächlich möglich ist!

Nehmen wir also an, wir brauchen nur Bits Genauigkeit in jedem Ausgabewert. Wie komplex ist die Berechnung der diskreten Fourier-Transformation als Funktion von n und b ? (Zur Vereinfachung können Sie annehmen, dass n eine Potenz von 2 ist .)$b$$n$$b$$n$$2$

Oder bedeutet jede Instanz von "FFT" in der Literatur tatsächlich "schnelle zahlentheoretische Transformation "? ^[2]

Siehe meine verwandten Fragen zur Komplexität der Gaußschen Eliminierung und zu den euklidischen kürzesten Wegen .

_{^[1] Es sollte wirklich der Gauß-Runge-König-Yates-Stumpf-Danielson-Lánczos-Cooley-Tukey-Algorithmus genannt werden.}

_{^[2] Und wenn ja, warum beschreiben die meisten Lehrbücher nur den Algorithmus für komplexe Zahlen?}

Diese Antwort ist eine Variante der Analyse des ersten Algorithmus ("Methode A") von Schönhage und Strassen zur Multiplikation langer Ganzzahlen.

Angenommen, wir wollen eine FFT der Länge berechnen . Skalieren Sie Ihre Eingabe so, dass alle Werte kleiner als 1 sind. Nehmen wir zunächst an, wir berechnen mit einer m- Bit-Festkomma-Arithmetik ( m Bits nach dem Binärpunkt ). Lassen δ = 2 1 / 2 - m die ( "Komplex") Einheit der dest Position sein. Sei ω = exp ( 2 π i / K ) .$K = 2^k$$m$$m$$\delta = 2^{1/2 -m}$$\omega = \exp(2\pi i/K)$

1) Man kann Näherungen so berechnen , dass | ω ' j - ω j | ≤ ( 2 k - 1 ) δ für alle 0 ≤ j ≤ K - 1 . Dies kann in der Zeit erfolgen O ( K M ( m ) ) , wo M ( m ) ist die benötigte Zeit zu multiplizieren m - Bit - Zahlen. (siehe Knuth Band 2, 3. Aufl., Seite 309).$\omega_j'$$|\omega_j' - \omega^j| \le (2k-1)\delta$$0 \le j \le K-1$$O(K M(m))$$M(m)$$m$

Wenn normaler ganzzahliger RAM logarithmische Kosten bedeutet, dann ist . Wenn Standard-Integer-RAM Wort-RAM bedeutet, ist M ( m ) = O ( m ) . (Schönhage und Strassen zeigen in "Methode A", wie die Multiplikation von m- Bit-Zahlen zu m- Multiplikation von O ( log m ) -Bit-Zahlen in linearer Zeit reduziert werden kann. Letzteres ist zu Stückkosten möglich.)$M(m) = O(m \log m)$$M(m) = O(m)$$m$$m$$O(\log m)$

2) Die klassische Cooley-Tukey-FFT berechnet Operationen der Form . Wir verwenden m -Bit - Festpunktarithmetik werden diese opertions a ' = t r u n c ein t e ( B ' + ω ' j c ' ) . Wenn wir b ' und c ' bis zu einem Fehler von ϵ kennen , erhalten wir a ' bis zu einem Fehler von 2 ϵ + $a = b + \omega^j c$$m$$a' = truncate(b' + \omega_j' c')$$b'$$c'$$\epsilon$$a'$ .$2\epsilon + 2k\delta$

3) Mit Hilfe der Induktion ist es leicht zu erkennen, dass wir das Endergebnis mit einem Fehler . Um am Ende die Genauigkeit b zu erhalten , ist m ≥ k + log k + b + O ( 1 ) . $(2^k - 1) \cdot 2k\delta$$b$$m \ge k + \log k + b + O(1)$

4) Somit ist die Endlaufzeit .$O(K k M(k+b))$

Dies sollte auch mit Gleitkommazahlen funktionieren: 1) kann immer noch mit Festkomma-Arithmetik durchgeführt werden, 2) gilt auch für Gleitkommazahlen.

In der Festkomma-Arithmetik geht es meiner Meinung nach sogar noch schneller. Zuerst reduzieren wir die Berechnung der FFT auf die Multiplikation von Polynomen mit Bluesteins Trick. Die Länge der Koeffizienten, die benötigt werden, um die gewünschte Genauigkeit zu erhalten, sollte . Dann reduzieren wir die Multiplikation von Polynomen auf die Multiplikation langer Ganzzahlen. (Hängen Sie die Koeffizienten an eine lange Zahl an und trennen Sie sie durch Nullblöcke der Länge O ( k + b ) .) Die Länge der ganzen Zahlen ist O ( K ( k + b ) ) .$O(k + b)$$O(k+b)$$O(K(k+b))$

Dies ist keine vollständige Antwort, aber ich kann Sie auf einige relevante Artikel verweisen und auch teilweise erklären, warum es nicht so einfach ist, eine Antwort auf Ihre spezifische Frage aus der Literatur zu extrahieren.

Lassen Sie mich zunächst fragen, warum Sie die Antwort auf diese Frage wissen möchten. Typischerweise sind die Leute, die sich für diese Art von Problem interessieren, mit der tatsächlichen Implementierung einer Hochleistungs-FFT für eine praktische Anwendung konfrontiert. Solche Leute interessieren sich weniger für asymptotische Komplexität in einem idealisierten Rechenmodell als für die Maximierung der Leistung unter ihren jeweiligen Hardware- und Software-Einschränkungen. Zum Beispiel schreiben die Entwickler der schnellsten Fourier-Transformation im Westen in ihrer Arbeit:

Die beste Wahl hängt von Hardwaredetails wie der Anzahl der Register, der Latenz und dem Durchsatz von Befehlen, der Größe und der Assoziativität von Caches, der Struktur der Prozessor-Pipeline usw. ab.

Dies sind Themen, mit denen sich Theoretiker normalerweise nicht abfinden wollen, die jedoch bei tatsächlichen Implementierungen von großer Bedeutung sind. Wenn ein Theoretiker erklärt: "Ich habe die absolut beste asymptotische Bit-Komplexität im RAM-Modell herausgefunden", könnte der Praktiker sagen: "Das ist schön", aber ein solches theoretisches Ergebnis kann für seine Zwecke unbrauchbar sein.

Trotzdem denke ich, dass Sie sich am besten die Literatur zur numerischen Analyse ansehen sollten. Beispielsweise haben Tasche und Zeuner die numerische Stabilität des FFT-Algorithmus unter die Lupe genommen. Dies ist möglicherweise immer noch nicht genau das, was Sie möchten, da der allgemeine Konsens unter den Praktikern zu sein scheint, dass es der beste praktische Ansatz ist, bestimmte Zahlen, die als "Twiddle-Faktoren" bezeichnet werden, mit hoher Genauigkeit vorab zu berechnen , um ein bestimmtes Maß an numerischer Präzision zu erzielen . Wenn Sie nur eine FFT durchführen, ist dies nicht der schnellste Ansatz, da Sie die Kosten Ihrer einmaligen Vorberechnung nicht über eine große Anzahl von FFT-Berechnungen amortisieren müssen. Ihre Analyse des Worst-Case-Abrundungsfehlers sollte dennoch für Ihre Frage relevant sein.