Angenommen, Sie haben zwei Polynome: und .
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.
Antworten:
Angenommen, wir verwenden die vierten Wurzeln der Einheit, was dem Ersetzen von x durch1,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,b↦a+b,a−b .) Daher ist die Transformation des ersten Polynoms
4,3+i,2,3−i.
Dies wird unter Verwendung vonX0,2=E0±O0 ,X1,3=E1∓iO1 . (Aus Zwillingsfaktorberechnung).
Machen wir dasselbe für das zweite Polynom. Die Koeffizienten sind2 , 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=(E1∓iO1)/2 . Wir haben die gewünschte Antwort erhalten
(3+x)(2+2x2)=6+2x+6x2+2x3.
quelle
Definieren Sie die Polynome, wo
deg(A) = q
unddeg(B) = p
. Diedeg(C) = q + p
.In diesem Fall
deg(C) = 1 + 2 = 3
.Wir können C in derO(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:
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, n ≥ de g( C) . Also ist n = 4 . Wenn Sie eine Zweierpotenz wählen, können Sie unseren Divide-and-Conquer-Algorithmus rekursiv anwenden.
SeiA′,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
Wir definierenM=Mn(ω) wobei ω komplexe Wurzeln sind nth komplexe Einheitswurzeln. Beachten Sie jth und in der Spalte kth ωjkn . Weitere Informationen zur DFT-Matrix finden Sie hier
n = 4
in diesem Beispiel. Beachten Sie auch, dass der Eintrag in der ZeileAusgehend von denω4= 4t h Wurzeln der Einheit haben wir die geordnete Mengengleichung:
Dies kann als Iteration durch die Wurzeln des Einheitskreises im Gegenuhrzeigersinn dargestellt werden .
Beachten Sie auch dieω6= ω6modn= ω2= - 1 und- i = ω3= ω3 + n
mod n
Natur, dhUm Schritt 1 ( Bewertung ) abzuschließen, finden wirEIN′, B′ durch Ausführen
Dieser Schritt kann mithilfe von D & C-Algorithmen erreicht werden (über den Rahmen dieser Antwort hinaus).
Schließlich besteht der letzte Schritt darin, C 'in Koeffizienten darzustellen. Beachten
HinweisM- 1n= 1nMn( ω- 1) 1undωj= - ωn / 2 + j .
quelle