Polynome und schnelle Fourier-Transformation
Mohsen TaheriFU Berlin – SoSe2012
Polynome und FFT2
Polynome Ein Polynom ist eine Funktion
Koeffizienten: Ein Polynom hat Grad k wenn der höchste
Koeffizient mit einem Wert ungleich 0 Länge = jede ganze Zahl großer als Grad eines
Polynoms
1
0)( n
jj
jxaxA
jaka
1GradLänge
Polynome und FFT3
Addition von Polynomen Seien und
Polynome der Länge n Addition von A(x) und B(x) ist
hat auch Länge n und Beispiel
Laufzeit:
1
0)( n
jj
j xaxA
1
0)( n
jj
jxbxB
1
0)( n
jj
j xcxC
jjj bac
39228
)2325(51238234
2334
xxxx
xxxxxx
)(n
Polynome und FFT4
Multiplikation von Polynomen Seien und
Polynome der Länge n Multiplikation von A(x) und B(x) ist Wobei Länge(C) = Länge(A) + Länge(B)
Beispiel
Laufzeit:
1
0)( n
jj
j xaxA
1
0)( n
jj
jxbxB
22
0)( n
jj
jxcxC
45867520441412
182014123640282445503530
)542)(91076(
23456
345623423
323
xxxxxx
xxxxxxxxxxx
xxxxx
j
k kjkj bac0
)( 2n
Polynome und FFT5
Darstellung von Polynomen Koeffizienten-Darstellung Point-Value-Darstellung
Polynome und FFT6
Koeffizienten-Darstellung Das Polynom als ein Vektor
der Koeffizienten Addition:
Laufzeit
Multiplikation (wie vorhin): wobei
Laufzeit
1
0)( n
jj
j xaxA),...,( 11,0 naaaa
),...,,( 110 naaaa ),...,,( 110 nbbbb
),...,,( 111100 nn babababac
),...,,( 1210 ncccc j
k kjkj bac0
)(n
)( 2n
Polynome und FFT7
Point-Value-Darstellung Polynom Länge n in Point-Value-
Darstellung: eine Menge von Punkten alle sind disjunkt für alle :
Auswertung durch Horne-Schema (in )
1
0)( n
jj
j xaxA
)},(),...,,(),,{( 111100 nn yxyxyx
kx)( kk xAy 1,...,1,0 nk
)(n
))...))((...(()( 1020201000 nn axaxaxaxaxA
Polynome und FFT8
Addition in Point-Value-Darstellung A : B :
Addition:
Laufzeit:
)},(),...,,(),,{( 111100 nn yxyxyx)},(),...,,(),,{( 111100 nn yxyxyx
)},(),...,,(),,{( 111111000 nnn yyxyyxyyxBAC
)(n
Polynome und FFT9
Multiplikation in Point-Value-Darstellung Problem: Länge(A.B)=Länge(A)+Länge(B) Lösung: Extended Point-Value
2n Punkte statt n Punkte A: B:
Multiplikation: C:
Laufzeit :
)},(),...,,(),,{( 12121100 nn yxyxyx)},(),...,,(),,{( 12121100 nn yxyxyx
)},(),...,,(),,{( 121212111000 nnn yyxyyxyyx
)(n
Polynome und FFT10
Evaluation Evaluation: Transform von Koeffizienten-
Vektor zur Point-Value-Darstellung Evaluating: Die Auswertung eines Polynoms
unter einen bestimmten Wert von x Mit Hilfe von Horne-Schema in
Evaluation insgesamt in
)(n
)( 2n
Polynome und FFT11
Interpolation Interpolation: Transform von Point-Value-
Darstellung zur Koeffizienten-Darstellung Lagranges Formel
1
0))(/)(()( n
kkj
jkkj
jk xxxxyxA
Polynome und FFT12
Theorem 1: Eindeutigkeit von Interpolation der Polynomen Für alle Menge von n Punkten mit disjunkt gibt es ein eindeutiges Polynom A(x) der
Länge n, so dass für alle
)},(),...,,(),,{( 111100 nn yxyxyx
kx
)( kk xAy 1,...,1,0 nk
Polynome und FFT13
DFT effiziente Methode für Evaluation und
Interpolation Diskrete Fourier Transform
Das Polynom in n komplexe n-te Einheitswurzeln auswerten
Eingabe: Koeffizienten-Vektor Ausgabe: Vektor
Auswertung der Polynom in n Komplexe n-te Einheitswurzeln
),...,,( 110 naaaa)(aDFTy n
),...,,( 110 nyyyy
1
0)( n
jj
j xaxA
Polynome und FFT14
Komplexe Einheitswurzeln komplexe Einheitswurzel: eine komplexe Zahl
wobei
Es gibt genau n komplexe n-te Einheitswurzeln: für k=0,1, … , n-1:
Die Zahl : primitive n-te Einheitswurzel alle anderen Zahlen sind die Potenzen dieser Zahl
n komplexe n-te Einheitswurzeln sind dann:
1n
nikk e /2
nin e /2
1210 ,...,,, nnnnn
Polynome und FFT15
Komplexe Einheitswurzeln - Eigenschaften Additive Gruppe
Die n Zahlen haben die gleiche Struktur wie die additive Gruppe
Beweis:
1210 ,...,,, nnnnn
nn mod),(
nkjn
kjn
kn
jnn
nn
mod0 1
Polynome und FFT16
Komplexe Einheitswurzeln - Eigenschaften Cancellation Lemma Für jede ganze Zahl gilt:
Beweis: .
Korollar: Für alle ganze Zahlen n>0 gilt:
0 und 0 ,0 dknkn
dkdn
kn
knikdkdnidkdn ee )()( /2/2
122/ n
n
Polynome und FFT17
Komplexe Einheitswurzeln - Eigenschaften Halving Lemma: wenn n>0 gerade Zahl die Quadrate der n komplexen n -te
Einheitswurzeln sind die n/2 komplexe (n/2)-te Einheitswurzeln: },...,,{})(,...,)(,){( 12/
2/1
2/0
2/212120 n
nnnnnnn
Polynome und FFT18
Komplexe Einheitswurzeln - Eigenschaften Halving Lemma: Beweis: Da n gerade ist, nehmen wir an n=2m Zu zeigen: Nach Cancellation Lemma:
da , ist dann , also
},...,,{})(,...,)(,){( 1102122
212
202
mmmm
mmmm
},...,,,,...,,{},...,,{ 1211101210 mm
mm
mm
mmmm
mmmm
},...,,{
},...,,,,...,,{},...,,,,...,,{110
110110121110
mmmm
mmmm
mmmm
mm
mm
mm
mmmm
1mm j
mjm
m
},...,,{})(,...,)(,){( 12102122
212
202
mmmm
mmmm
□
Polynome und FFT19
Komplexe Einheitswurzeln - Eigenschaften Summation Lemma: Für jede ganze Zahl n≥1 und für k≠0 und
nicht dividierbar durch n, gilt: 0)(1
0
n
jjk
n
Polynome und FFT20
FFT Evaluation eines Polynoms in
unter Verwendung der Eigenschaften der Einheitswurzeln
Diese Methode heißt Fast Fourier Transform(FFT).
Annahme n ist ein 2er Potenz ( ) Divide-and-Conquer
)lg( nn
kn 2
Polynome und FFT21
FFT das Polynom A(x) in gerade und ungerade
indizierte Koeffizienten teilen zwei neue Polynome der
Länge n/2
Das Polynom wird so berechnet:
)(),( ]1[]0[ xAxA
12/1
2531
]1[
12/2
2420
]0[
...)(
...)(
n
n
nn
xaxaxaaxA
xaxaxaaxA
)()()( 2]1[2]0[ xxAxAxA
Polynome und FFT22
FFT das Problem von Auswerten des Polynoms in n
Punkten ( ) reduziert zu:
1. zwei Polynome der Länge n/2 in Punkten ( ) auswerten
2. das Resultat mit Hilfe der Abgleichung
zusammen addieren
212120 )(,...,)(,)( nnnn
110 ,...,, nnnn
)(),( ]1[]0[ xAxA
)()()( 2]1[2]0[ xxAxAxA
Polynome und FFT23
FFT Nach Halving Lemma:
die Anzahl der Elemente der Liste nicht n, sondern n/2.
Die zwei Subprobleme haben genau die gleiche Struktur wie das ursprüngliche Problem und sind halb so groß.
212120 )(,...,)(,)( nnnn
Polynome und FFT24
Rekursiv FFTRECURSIVE-FFT(a)1. n = a.length()2. if n==1 3. return a4. 5. 6. 7. 8. 9. 10. for k=0 to n/2-111. 12. 13. 14. return y
1
nin e /2
),...,,( 220]0[
naaaa
),...,,( 131]1[
naaaa)( ]0[]0[ aFFTRECURSIVEy )( ]1[]1[ aFFTRECURSIVEy
]1[]0[kkk yyy
]1[]0[)2/( kknk yyy
n
),...,,( 110 naaaa)(aDFTy n
Eingabe:Ausgabe:
Polynome und FFT25
Rekursiv FFT Zeilen11-12 kombinieren das Ergebnis der
rekursiven Berechnung Zeile 11 für
Zeile 12 für
zusammengefügt wird Vektor y berechnet
2/nDFT
12/10 ,..., nyyy)()()( 2]1[2]0[]1[]0[ k
nkn
kn
knk
knkk AAAyyy
112/2/ ,..., nnn yyy
)()()(
)()()2/(2]1[)2/(2]0[
2]1[)2/(2]0[
]1[2/]0[]1[]0[)2/(
nkn
nkn
nkn
nkn
kn
nkn
kn
knk
nkkknknk
AAA
AA
yyyyy
Polynome und FFT26
Rekursiv FFT - Laufzeit jeder rekursiver Aufruf kostet
n = Länge des Eingabevektors Laufzeit:
)(n
)lg()()2/(2)( nnnnTnT
Polynome und FFT27
Interpolation in Einheitswurzeln umgekehrtes Verfahren
Polynom vom Point-Value zurück zu Koeffizienten Berechnung von DTF als eine
Matrizenmultiplikation
Vandermonde-Matrix wir brauchen die Inverse-Matrix
)(1 yDFTa
1
3
2
1
0
)1)(1()1(3)(21
)1(3963
)1(2642
132
1
3
2
1
0
1
111
11111
)(
nnn
nn
nn
nnn
nnnnn
nnnnn
nnnnn
n a
aaaa
y
yyyy
aDFT
nV1
nV
yVaaVy nn .. 1
Polynome und FFT28
Inverse von Vandermonde-Matrix Theorem: Für j,k=0,1,…,n-1 sind die
(j,k)Einträge von die Zahlen Beweis:
z.z.: , wobei die n×n Identitätsmatrix betrachte die (j,j')Einträge von
Falls j=j‘ : Falls j≠j‘ :
-(n-1) ≤ j-j' ≤ n-1 j-j' ist nicht durch n dividierbar Summation Lemma :
1nV
nkjn /
nnn IVV 1nI
nn VV 1
1
0)'(1
0'
'1 )/())(/(][ n
kjjk
nn
kkjn
kjnjjnn nnVV
1)/(1
0)'(
n
kjjk
n n
0)/(1
0)'(
n
kjjk
n n
Polynome und FFT29
Interpolation in Einheitswurzeln I : (j,k)Einträge der sind: II :
Vergleiche mit Polynom in Einheitswurzeln leichte Modifikation in Algorithmus berechnet die
Interpolation tausche a und y ersetze durch dividiere jedes Element durch n
Also die Interpolation auch in berechenbar
yVa n .1nV kj
njkn /][ 1 1nV
1
0
1 n
kkjnkj y
naIII
1
0
n
kknkk ay
n 1n
)lg( nn
Polynome und FFT30
Zusammenfassung
221,0 ,..., nccc
)(),(
)(),(
)(),(
122
122
12
12
02
02
nn
nn
nn
nn
BA
BA
BA
Koeffizienten-Darstellung
Point-Value-Darstellung
)(
)(
)(
122
12
02
nn
n
n
C
C
C
Standard-Multiplikation
Laufzeit
EvaluationLaufzeit
InterpolationLaufzeit
punktweise Multiplikation
Laufzeit
)lg( nn)lg( nn
)( 2n
)(n
110
11,0
,...,,
,...,
n
n
bbb
aaa