Zeigen Sie, wie man FFT von Hand macht

27

Angenommen, Sie haben zwei Polynome: 3+x und 2x2+2 .

Ich versuche zu verstehen, wie FFT uns hilft, diese beiden Polynome zu multiplizieren. Ich kann jedoch keine ausgearbeiteten Beispiele finden. Kann mir jemand zeigen, wie der FFT-Algorithmus diese beiden Polynome multiplizieren würde. (Hinweis: Diese Polynome haben nichts Besonderes, aber ich wollte es einfach halten, damit es leichter zu verfolgen ist.)

Ich habe mir die Algorithmen im Pseudocode angesehen, aber alle scheinen Probleme zu haben (keine Angabe, wie die Eingabe lauten soll, undefinierte Variablen). Und überraschenderweise kann ich nicht finden, wo jemand tatsächlich (von Hand) ein Beispiel für die Multiplikation von Polynomen mit FFT durchgegangen ist.

lars
quelle
2
Wikipedia behält dieses schöne Bild für die Ganzzahlmultiplikation per FFT bei, aber ich denke, eine noch ausführlichere Schritt-für-Schritt-Anleitung könnte hilfreich sein.
Realz Slaw

Antworten:

27

Angenommen, wir verwenden die vierten Wurzeln der Einheit, was dem Ersetzen von x durch 1,i,1,i . Wir verwenden im FFT-Algorithmus auch die zeitliche Dezimierung anstelle der Frequenzdezimierung. (Wir wenden auch nahtlos eine Bitumkehroperation an.)x

Um die Transformation des ersten Polynoms zu berechnen, schreiben wir zunächst die Koeffizienten:

3,1,0,0.
Die Fouriertransformation der geraden Koeffizienten 3,0 ist 3,3 und der ungeraden Koeffizienten 1,0 ist 1,1 . (Diese Transformation ist nur a,ba+b,ab .) Daher ist die Transformation des ersten Polynoms
4,3+i,2,3i.
Dies wird unter Verwendung vonX0,2=E0±O0 ,X1,3=E1iO1 . (Aus Zwillingsfaktorberechnung).

Machen wir dasselbe für das zweite Polynom. Die Koeffizienten sind

2,0,2,0.
Die geraden Koeffizienten 2,2 transformieren sich zu 4,0 und die ungeraden Koeffizienten 0,0 transformieren sich zu 0,0 . Daher ist die Transformation des zweiten Polynoms
4,0,4,0.

Wir erhalten die Fourier-Transformation des Produktpolynoms, indem wir die beiden Fourier-Transformationen punktweise multiplizieren:

16,0,8,0.
Es bleibt die inverse Fourier-Transformation zu berechnen. Die geraden Koeffizienten 16,8 transformieren sich invers zu 12,4 und die ungeraden Koeffizienten 0,0 transformieren sich invers zu 0,0 . (Die inverse Transformation ist x,y(x+y)/2,(x-y)/2 ) Daher ist die Transformation des Produktpolynoms
6,2,6,2.
Dies wird erhalten unter Verwendung vonX0,2=(E0±O0)/2 ,X1,3=(E1iO1)/2 . Wir haben die gewünschte Antwort erhalten
(3+x)(2+2x2)=6+2x+6x2+2x3.

Yuval Filmus
quelle
wie bist du zu 6,2 6, 2 gekommen?
Lars
Ich gab die Formeln an: , X 1 , 3 = ( E 1i O 1 ) / 2 , wobei E 0 , E 1 ( O 1 , O 2 ) ist die inverse Transformation der geraden (ungeraden) Koeffizienten, erhalten durch die Formel x , y ( x + y )X0,2=(E0±O2)/2X1,3=(E1iO1)/2E0,E1O1,O2 . Bitte schauen Sie sich die Antwort noch einmal an - alle Berechnungen sind da. x,y(x+y)/2,(xy)/2
Yuval Filmus
Warum verwenden Sie die geraden Koeffizienten zweimal? 3,3 -> 3,3,3,3. -> 3 + 1, 3-i, 3 + -1,3 - i?
Aage Torleif
Wie erstrecken sich diese Formeln für und X 1 , 3 zu höheren Graden? Kippen die Plus- / Minuszeichen einfach weiter? Was wäre es zum Beispiel für X 0 , 2 , 4 ? X0,2X1,3X0,2,4
Bobby Lee
@BobbyLee Ich ermutige Sie, etwas Literatur über FFT zu lesen.
Yuval Filmus
7

Definieren Sie die Polynome, wo deg(A) = qund deg(B) = p. Die deg(C) = q + p.

In diesem Fall deg(C) = 1 + 2 = 3.

A=3+xB=2x2+2C=AB=?

Wir können C in der O(n2) -Zeit leicht durch Brute-Force-Multiplikation von Koeffizienten finden. Durch Anwenden von FFT (und inverser FFT) können wir dies in O(nlog(n)) Zeit erreichen. Ausdrücklich:

  1. Konvertieren Sie die Koeffizientendarstellung von A und B in ihre Wertdarstellung. Diesen Vorgang nennt man Auswertung . Das Durchführen von Divide-and-Conquer (D & C) dafür würde O(nLog(n)) Zeit in Anspruch nehmen .
  2. Multiplizieren Sie die Polynome in ihrer Wertedarstellung komponentenweise. Dies gibt die Wertedarstellung von C = A * B zurück. Dies braucht O(n) Zeit.
  3. Invertiere C mit inverser FFT, um C in seiner Koeffizientendarstellung zu erhalten. Dieser Vorgang wird als Interpolation bezeichnet und benötigt auch O(nLog(n)) Zeit.

Im weiteren Verlauf stellen wir jedes Polynom als einen Vektor dar, dessen Wert seine Koeffizienten sind. Wir füllen den Vektor mit 0en auf bis zur kleinsten Potenz von zwei, n=2k,ndeG(C) . Also ist n=4 . Wenn Sie eine Zweierpotenz wählen, können Sie unseren Divide-and-Conquer-Algorithmus rekursiv anwenden.

EIN=3+x+0x2+0x3ein=[3,1,0,0]B=2+0x+2x+0x3b=[2,0,2,0]

Sei EIN,B die Wertrepräsentation von A bzw. B. Beachten Sie, dass FFT (Fast Fourier Transform ) eine lineare Transformation ( lineare Abbildung ) ist und als Matrix M . Somit

EIN=MeinB=Mb

Wir definieren M=Mn(ω) wobei ω komplexe Wurzeln sind nth komplexe Einheitswurzeln. Beachten Sie n = 4in diesem Beispiel. Beachten Sie auch, dass der Eintrag in der Zeile jth und in der Spalte kthωnjk . Weitere Informationen zur DFT-Matrix finden Sie hier

M4(w)=[111...11ω1ω2...ωn-11ω2ω4...............ωjk...1ωn-1ω2(n-1)...ω(n-1)(n-1)]=[11111ωω2ω31ω2ω4ω61ω3ω6ω9]

Ausgehend von den ω4=4th Wurzeln der Einheit haben wir die geordnete Mengengleichung:

{ω0,ω1,ω2,ω3,ω4,ω5,...}={1,ich,-1,-ich,1,ich,...}

Dies kann als Iteration durch die Wurzeln des Einheitskreises im Gegenuhrzeigersinn dargestellt werden .

Beachten Sie auch die mod nNatur, dh ω6=ω6modn=ω2=-1und-ich=ω3=ω3+n

Um Schritt 1 ( Bewertung ) abzuschließen, finden wir EIN,B durch Ausführen

EIN=Mein=[11111ωω2ω31ω2ω4ω61ω3ω6ω9][3100]=[3+13+1ω3+ω23+ω3]=[43+ich23-ich]B=Mb=[11111ωω2ω31ω2ω4ω61ω3ω6ω9][2020]=[2+22+2ω22+2ω42+2ω6]=[4040]

Dieser Schritt kann mithilfe von D & C-Algorithmen erreicht werden (über den Rahmen dieser Antwort hinaus).

EINB komponentenweise multiplizieren (Schritt 2)

EINB=[43+ich23-ich][4040]=[16080]=C

Schließlich besteht der letzte Schritt darin, C 'in Koeffizienten darzustellen. Beachten

C=McM-1C=M-1Mcc=M-1C

Hinweis Mn-1=1nMn(ω-1)1undωj=-ωn/2+j.

Mn-1=14[11111ω-1ω-2ω-31ω-2ω-4ω-61ω-3ω-6ω-9]=14[11111-ich-1ich1-11-11ich-1-ich]

ω-j

{ω0,ω1,ω2,ω3,ω4,ω5,...}={1,i,1,i,1,i,...}

nthωj=ωnj

c=M1C=1nMn(w1)=14[11111i1i11111i1i][16080]=[(16+8)/4(168)/4(16+8)/4(168)/4]=[6262]

C=AB=6+2x+6x2+2x3

j__gt
quelle