Upload
cain-petersen
View
34
Download
0
Embed Size (px)
DESCRIPTION
Algorithmentheorie 02 - Polynomprodukt und Fast Fourier Transformation. Prof. Dr. S. Albers Prof. Dr. Th. Ottmann. 1. Polynome. Reelles Polynom p in einer Variablen x p(x) = a n x n + ... +a 1 x 1 + a 0 a 0 ,..., a n R , a n 0: Koeffizienten von p - PowerPoint PPT Presentation
Citation preview
WS 03/04 1
Algorithmentheorie
02 - Polynomprodukt und Fast Fourier Transformation
Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
2WS 03/04
1. Polynome
Reelles Polynom p in einer Variablen x
p(x) = anxn + ... +a1x1 + a0
a0 ,..., an R, an 0: Koeffizienten von p
Grad von p: höchste Potenz in p (= n)
Beispiel:
p(x) = 3x3 – 15x2 + 18x
Menge aller reellen Polynome: R[x]
3WS 03/04
2. Operationen auf Polynomen
1. Addition
0
1
1
0
1
1
bxbxbxqaxaxaxp
n
n
n
n
00
1
11
00
baxbaxbabxbaxaxqxp
n
nn
n
n
n
n
][, xRqp
4WS 03/04
Operationen auf Polynomen
2. Produkt
c i : Welche Monomprodukte haben Grad i?
Polynomring R[x]
0
1
1
2
2
00
cxcxcbxbaxaxqxp
n
n
n
n
n
n
0,0
.2,...,0
2121
0
nnnn
i
jjiji
bbaa
nibac
5WS 03/04
Operationen auf Polynomen
3. Auswerten an der Stelle x0: Horner-Schema
Zeit: O(n)
0010100
axaxaxaxpnn
6WS 03/04
3. Repräsentation eines Polynoms
p(x) R[x]
Möglichkeit zur Repräsentation von p(x):
1. Koeffizientendarstellung
Beispiel:
0
1
1axaxaxp n
n
xxxxp 18153 23
7WS 03/04
Repräsentation eines Polynoms
2. Nullstellenprodukt
p(x) R[x]
Beispiel:
nn
xxxxaxp 1
323 xxxxp
8WS 03/04
Repräsentation eines Polynoms
3. Punkt/Wertdarstellung
Interpolationslemma
Jedes Polynom p(x) aus R[x] vom Grad n ist eindeutig bestimmt
durch n+1 Paare (xi, p(xi)), mit i = 0,...,n und xi xj für i j
Beispiel:
Das Polynom
wird durch die Paare (0,0), (1,6), (2,0), (3,0) eindeutig festgelegt.
323 xxxxp
9WS 03/04
Operationen auf Polynomen
p, q R[x], Grad(p) = Grad(q) = n
Koeffizientendarstellung
Addition: O(n)
Produkt: O(n2)
Auswertung an der Stelle x0: O(n)
Punkt/Wertdarstellung
nn
nn
zxzxzxq
yxyxyxp
,,,,,,
,,,,,,
1100
1100
10WS 03/04
Operationen auf Polynomen
Addition:
Zeit: O(n)
Produkt:
(Voraussetzung: n Grad(pq))
Zeit: O(n)
Auswerten an der Stelle x´: ??Umwandeln in Koeffizientendarstellung(Interpolation)
nnn
zyxzyxzyxqp ,,,,,,111000
nnn
zyxzyxzyxqp ,,,,,,111000
11WS 03/04
Polynomprodukt
Berechnung des Produkts zweier Polynome p, q vom Grade < n
p,q Grad n-1, n KoeffizientenAuswertung:
2n Punkt/Wertpaare und
Punktweise Multiplikation
2n Punkt/Wertpaare
Interpolation
pq Grad 2n-2, 2n-1 Koeffizienten
ii
xpx , ii
xqx ,
ii
xpqx ,
1210 ,,, nxxx
12WS 03/04
Ansatz für Divide and Conquer
Idee: (n sei gerade)
2
12
0
2/221
231
2/222
220
11
331
22
220
1110
xxpxp
xaxaax
xaxaa
xaxaxa
xaxaa
xaxaaxp
n
n
n
n
nn
nn
nn
13WS 03/04
Repräsentation von p(x)
Annahme: Grad(p) < n
3a. Werte an den n Potenzen der n-ten komplexen Haupteinheitswurzel
Potenz von n (Einheitswurzeln):
1 =
110 ,,, n
nnn 10
8
1
8
2
8
3
8
4
8
5
8
6
8
7
8
nien/2
1i 12 ie
14WS 03/04
Diskrete Fourier Transformation
Werte von p für die n Potenzen von n legen p eindeutig
fest, falls Grad(p)<n.
Diskrete Fourier Transformation (DFT)
Beispiel: n=4
110 ,,,)( n
nnnnppppDFT
iie
ie
iie
ie
xixe
i
i
i
i
ix
2/3sin2/3cos
1sincos
)2/sin()2/cos(
1)0sin()0cos(
sincos
34/234
24/224
4/214
004
15WS 03/04
Auswertung an den Einheitswurzeln
i1
4
10
412
4
i3
4
xxxxp 18153 23
16WS 03/04
Auswertung an den Einheitswurzeln
61110
4
0
4, , p ω, pω
i i, ii, p ω, pω 15151
4
1
4
361112
4
2
4, -- -, p- ω, pω
i --i, -i-i, p ω, pω 15153
4
3
4
iipDFT 1515,36,1515,64
17WS 03/04
Polynomprodukt
Berechnung des Produkts zweier Polynome p, q vom Grade < n
p,q Grad n-1, n KoeffizientenAuswertung:
2n Punkt/Wertpaare und
Punktweise Multiplikation
2n Punkt/Wertpaare
Interpolation
pq Grad 2n-2, 2n-1 Koeffizienten
12
2
1
2
0
2 ,,, n
nnn
i
n
i
n p 22 , i
n
i
n q 22 ,
i
n
i
n pq 22 ,
18WS 03/04
4. Eigenschaften der Einheitswurzel
bilden eine multiplikative Gruppe
KürzungslemmaFür alle n > 0, 0 k n, und d > 0 gilt:
Beweis:
Folge:
12
2
1
2
0
2 ,,, n
nnn
k
n
dk
dn
k
n
nikdnidkdk
dn ee /2/2
11
22 n
n
19WS 03/04
Eigenschaften der Einheitswurzel
Halbierungslemma
Die Menge der Quadrate der 2n komplexen 2n-ten
Einheitswurzeln
ist gleich der Menge der n komplexen n-ten
Einheitswurzeln
Beweis:
212
2
21
2
20
2,,, n
nnn
110 ,,, n
nnn
kk
n
k
n 2
2
2
2
2
,,,,,...,,2
2
2
2
21
2
20
2
10
kn
kn
nn
knn
knnn
kn
n
k
nnn
20WS 03/04
Eigenschaften der Einheitswurzel
Summationslemma
Für alle n > 0, j 0 mit
Beweis:
01
0
n
k
jk
n
jn |
0
1
1
1
11
0
j
n
jnn
jn
njn
n
k
kjn
21WS 03/04
5. Diskrete Fourier Transformation
Fast Fourier Transformation:
Berechnung von DFTn(p) mittels
eines Divide-and-Conquer Ansatzes
110 ,,,)( n
nnnnppppDFT
22WS 03/04
Diskrete Fourier Transformation
Idee: (n sei gerade)
2/2
1311
2/2
2200
n
n
n
n
xaxaaxp
xaxaaxp
2
12
0
2/221
231
2/222
220
11
331
22
220
1110
xxpxp
xaxaax
xaxaa
xaxaxa
xaxaa
xaxaaxp
n
n
n
n
nn
nn
nn
23WS 03/04
Diskrete Fourier Transformation
Auswertung für k = 0, ... , n – 1
2
1
2
0
k
n
k
n
k
n
k
nppp
2/ falls
2/ falls
,
2/
2/1
2/
2/0
2/12/0
nk
pp
nk
pp
nk
n
k
n
nk
n
k
n
k
n
k
n
24WS 03/04
Diskrete Fourier Transformation
Beispiel:
)()()( 0
21
0
4
0
20
0
4 ppp
)()()( 1
21
1
4
1
20
1
4 ppp
)()()( 0
21
2
4
0
20
2
4 ppp
)()()( 1
21
3
4
1
20
3
4 ppp
25WS 03/04
Berechnung von DFTn
Einfachster Fall: n = 1 (Grad(p) = n –1 = 0)
DFT1(p) = a0
Sonst :
Divide:
Teile p in p0 und p1 auf
Conquer:
Berechne DFTn/2(p0) und DFTn/2(p1) rekursiv
Merge:
Berechne für k = 0, ... , n –1:
DFTn(p)k =
110 ,,,)( n
nnnnppppDFT
knn
k
n
knn
pDFTpDFT
pDFTpDFT
))(),((
))(),((
12/12/
02/02/
26WS 03/04
Eine kleine Verbesserung
Also falls k < n/2:
k
n
k
n
k
n
k
nppp
2/12/0
2/
2/12/0
nk
n
k
n
k
n
k
nppp
2/ falls
2/ falls
,
2/
2/1
2/
2/0
2/12/0
nk
pp
nk
pp
pnk
n
k
n
nk
n
k
n
k
n
k
n
k
n
2/ falls
,
2/ falls
,
2/
2/1
2/2/
2/0
2/12/0
nk
pp
nk
pp
nk
n
nk
n
nk
n
k
n
k
n
k
n
27WS 03/04
Eine kleine Verbesserung
Beispiel:
)()()( 0
21
0
4
0
20
0
4 ppp
)()()( 1
21
1
4
1
20
1
4 ppp
)()()( 0
21
0
4
0
20
2
4 ppp
)()()( 1
21
1
4
1
20
3
4 ppp
28WS 03/04
6. Fast Fourier Transformation
Algorithmus FFTInput: Ein Array a mit den n Koeffizienten eines Polynoms p
und n = 2k
Output: DFTn(p) 1. if n = 1 then /* p ist konstant */2. return a
3. d[0] = FFT([a0, a2, ... , an-2 ], n/2)
4. d[1] = FFT([a1, a3, ... , an-1], n/2)
5. n = e2i/n
6. = 1
7. for k = 0 to n/2 – 1 do /* = nk*/
11. return d
10.
.9
8.
n
102/
10
kknk
kkk
ddd
ddd
29WS 03/04
FFT : Beispiel
a = [0, 18,-15, 3 ]a[0] = [0, -15] a[1] = [18, 3]FFT([0, -15], 2) = (FFT([0],1) + FFT([-15],1), FFT([0],1) - FFT([-15],1)) = (-15,15)FFT([18, 3],2) = (FFT([18],1) + FFT([3],1), FFT([18],1) - FFT([3],1)) = (21,15)
k = 0 ; = 1
d0 = -15 + 1 * 21 = 6 d2 = -15 – 1 * 21 = -36
k = 1 ; = i
d1 = 15 + i*15 d3 = 15 – i*15
FFT(a, 4) = (6, 15+15i, -36, 15 –5i)
018153 23 xxxxp
30WS 03/04
7. Analyse
T(n) = Zeit um ein Polynom vom Grad < n an den Stellen
auszuwerten.
T(1) = O(1)
T(n) = 2 T(n/2) + O(n)
= O(n log n)
12
2
1
2
0
2 ,,, n
nnn
31WS 03/04
Polynomprodukt
Berechnung des Produkts zweier Polynome p, q vom Grade < n
p,q Grad n-1, n KoeffizientenAuswertung durch FFT:
2n Punkt/Wertpaare und
Punktweise Multiplikation
2n Punkt/Wertpaare
Interpolation
pq Grad 2n-2, 2n-1 Koeffizienten
122
12
02 ,,, n
nnn
i
n
i
n p 22 , i
n
i
n q 22 ,
i
n
i
n pq 22 ,
32WS 03/04
Interpolation
Umrechnung der Punkt/Wert-Darstellung in dieKoeffizientendarstellung
Gegeben: (x0, y0),..., (xn-1, yn-1) mit xi xj, für alle i j
Gesucht: Polynom p mit Koeffizienten a0,..., an-1, so dass
1
1
111101
2
1
212102
1
1
111101
0
1
010100
n
n
nnnn
n
n
n
n
n
n
yxaxaaxp
yxaxaaxpyxaxaaxpyxaxaaxp
33WS 03/04
Interpolation
Matrixschreibweise
1
1
0
1
1
0
1
11
1
21
1
00
1
1
1
nn
n
nn
n
n
y
y
y
a
a
a
xx
xx
xx
34WS 03/04
Interpolation
Spezialfall (hier) : Definition:
jixx
y
y
y
a
a
a
xx
xx
xx
ji
nn
n
nn
n
n
allefür ,für lösbar ist
1
1
1
systemGleichungs
1
1
0
1
1
0
1
11
1
11
1
00
V
, ,
1
n
,
yVaya
yyaaV
n
iiji
ij
nn
i
nix
35WS 03/04
Interpolation
SatzFür alle 0 i, j n – 1 gilt:
n
Vij
n
ijn
1
Beweis
ji
ijn
n nV
,
1
zu zeigen:
nnnIVV 1
36WS 03/04
Interpolation
ij
jn
n
j
n
j
nni
n
i
n
ijnn
nn
nnn
VV
jiVV
)1(
2
)1(
1
1
1
1
: Spalte , in Zeile von Eintrag Betrachte
37WS 03/04
Interpolation
1
0
)(1
0
1 1 n
k
kji
n
n
k
jk
n
ik
n
ijnn nnVV
Fall 1: i = j
1
0
01
01
11 n
k
k
n
n
k
kji
n nn
Fall 2: i j, : | damit
und 11 d.h. jin
njin
1
00
1 n
k
kji
nn
38WS 03/04
Interpolation
Summationslemma
:gilt |mit 0,0 alleFür jnjn
1
00
n
k
jkn
39WS 03/04
Interpolation
1
0
1
0
1
1
0
1
1
1
,,,1
n
k
kink
n
k
ikn
k
n
nin
in
ini
yn
ny
y
y
y
nnn
yVa
40WS 03/04
Interpolation
)1(10
1
1
2
210
1
0
1
0
11
0
10
,,,1
,,,1
n
nnn
n
n
n
k
n
k
kn
nk
kn
k nk
k
nk
rrrn
a
xyxyxyyxr
yyyn
a
41WS 03/04
Interpolation und DFT
0 )(1
irDFTn
a inni
)1(10 ,,,1 n
nnnrrr
na
11 ,,,1
nnn
nn rrr
na 1n
ndenndenn
)(1
00 rDFTn
a n
42WS 03/04
Polynomprodukt durch FFT
Berechnung des Produkts zweier Polynome p, q vom Grade < n
p,q Grad n-1, n KoeffizientenAuswertung durch FFT:
2n Punkt/Wertpaare und
Punktweise Multiplikation
2n Punkt/Wertpaare
Interpolation durch FFT
pq Grad 2n-2, 2n-1 Koeffizienten
122
12
02 ,,, n
nnn
i
n
i
n p 22 , i
n
i
n q 22 ,
i
n
i
n pq 22 ,