Algorithmentheorie

02 - Polynomprodukt undFast Fourier Transformation

Robert Elsässer

2

1. Polynome

Reelles Polynom p in einer Variablen xp(x) = anxn + ... +a1x1 + a0

a0 ,..., an ∈ R, an ≠ 0: Koeffizienten von pGrad von p: höchste Potenz in p (= n)

Beispiel:

p(x) = 3x3 – 15x2 + 18x

Menge aller reellen Polynome: R[x]

3

2. Operationen auf Polynomen

1. Addition

( )( ) 0

11

01

1

bxbxbxqaxaxaxp

nn

nn

+++=+++=

KK

( ) ( ) ( ) ( )( ) ( ) ( )00

111

00

baxbaxbabxbaxaxqxp

nnn

nn

nn

++++++=+++++=+

KKK

][, xRqp ∈

4

Operationen auf Polynomen

2. Produkt

c i : Welche Monomprodukte haben Grad i ?

Polynomring R[x]

( ) ( ) ( )( )0

11

22

00

cxcxcbxbaxaxqxp

nn

nn

nn

+++=++++=

KKK

0,0

.2,...,0

2121

0

======

==⇒

++

= −∑

nnnn

i

j jiji

bbaa

nibac

KK

5

Operationen auf Polynomen

3. Auswerten an der Stelle x0: Horner-Schema

Zeit: O(n)

( ) ( )( ) 0010100 axaxaxaxp nn ++++= − KK

6

3. Repräsentation eines Polynoms

p(x) ∈ R[x]

Möglichkeit zur Repräsentation von p(x):

1. Koeffizientendarstellung

Beispiel:

( ) 01

1 axaxaxp nn +++= K

( ) xxxxp 18153 23 +−=

7

Repräsentation eines Polynoms

2. Nullstellenprodukt

p(x) ∈ R[x]

Beispiel:

( ) ( ) ( )nn xxxxaxp −−= K1

( ) ( )( )323 −−= xxxxp

8

Repräsentation eines Polynoms

3. Punkt/Wertdarstellung

InterpolationslemmaJedes Polynom p(x) aus R[x] vom Grad n ist eindeutig bestimmtdurch 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

9

Operationen auf Polynomen

p, q ∈ R[x], Grad(p) = Grad(q) = n

KoeffizientendarstellungAddition: O(n)Produkt: O(n2)Auswertung an der Stelle x0: O(n)

Punkt/Wertdarstellung

( ) ( ) ( )

( ) ( ) ( )nn

nn

zxzxzxq

yxyxyxp

,,,,,,

,,,,,,

1100

1100

K

K

=

=

10

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 K

( ) ( ) ( )nnn zyxzyxzyxqp ⋅⋅⋅=⋅ ,,,,,, 111000 K

11

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 K

12

Ansatz für Divide and ConquerIdee: (n sei gerade)

( )

( )( )

( )( )( )( ) ( )2

12

0

2/221

231

2/222

220

11

331

22

220

1110

xxpxp

xaxaax

xaxaa

xaxaxa

xaxaa

xaxaaxp

nn

nn

nn

nn

nn

+=

+++

++++=

+++

++++=

+++=

−

−

−

−

−−

−−

−−

K

K

K

K

K

13

Repräsentation von p(x)

Annahme: Grad(p) < n

3a. Werte an den n Potenzen der n-ten komplexenHaupteinheitswurzel

Potenz von ωn (Einheitswurzeln):

1 = 110 ,,, −nnnn ωωω K 10

8 =ω

18ω

28ω

38ω

48ω

58ω

68ω

78ω

nien /2πω =

1−=i 12 =ie π

14

Diskrete Fourier Transformation

Werte von p für die n Potenzen von ωn legen p eindeutigfest, falls Grad(p)<n.

Diskrete Fourier Transformation (DFT)

Beispiel: n=4

( ) ( ) ( )( )110 ,,,)( −= nnnnn ppppDFT ωωω K

( )( ) ( ) ( ) iie

ie

iieie

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

ππω

ππω

ππω

ω

π

π

π

15

Auswertung an den Einheitswurzeln

i=14ω

104 =ω12

4 −=ω

i−=34ω

16

Auswertung an den Einheitswurzeln

( )( ) ( )( ) ( )611104

04 ,, p ω, pω ==

( )( ) ( )( ) ( )ii, ii, p ω, pω 151514

14 +==

( )( ) ( )( ) ( )3611124

24 , ---, p- ω, pω ==

( )( ) ( )( ) ( )i--i, -i-i, p ω, pω 151534

34 ==

( ) ( )iipDFT 1515,36,1515,64 −−+=

( ) xxxxp 18153 23 +−=

17

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

122

12

02 ,,, −n

nnn ωωω K

( )( )in

in p 22 , ωω ( )i

nq 2( )in2 , ωω

( )( )in

in pq 22 , ωω

18

4. Eigenschaften der Einheitswurzel

bilden eine multiplikative Gruppe

KürzungslemmaFür alle n > 0, 0 ≤ k ≤ n, und d > 0 gilt:

Beweis:

Folge:

122

12

02 ,,, −n

nnn ωωω K

kn

dkdn ωω =

( ) kn

nikdnidkdkdn ee ωω ππ === /2/2

1122 −==ωω n

n

19

5. Diskrete Fourier Transformation

Fast Fourier Transformation:

Berechnung von DFTn(p) mittels eines Divide-and-Conquer Ansatzes

( ) ( ) ( )( )110 ,,,)( −= nnnnn ppppDFT ωωω K

20

Diskrete Fourier Transformation

Idee: (n sei gerade)

( ) ( )

( ) ( ) 2/21311

2/22200

−

−

−

−

+++=+++=

nn

nn

xaxaaxpxaxaaxp

K

K

( )

( )( )

( )( )( )( ) ( )2

12

0

2/221

231

2/222

220

11

331

22

220

1110

xxpxp

xaxaax

xaxaa

xaxaxa

xaxaa

xaxaaxp

nn

nn

nn

nn

nn

+=

+++

++++=

+++

++++=

+++=

−

−

−

−

−−

−−

−−

K

K

K

K

K

21

Diskrete Fourier Transformation

Auswertung für k = 0, ... , n – 1

( ) ( )( ) ( )( )2

1

2

0kn

kn

kn

kn ppp ωωωω +=

( ) ( )

( ) ( )⎪⎪⎩

⎪⎪⎨

⎧

≥+<

+

=−−

2/ falls

2/ falls,

2/2/1

2/2/0

2/12/0

nkppnkpp

nkn

kn

nkn

kn

kn

kn

ωωω

ωωω

22

Diskrete Fourier Transformation

Beispiel:

)()()( 021

04

020

04 ωωωω ppp +=

)()()( 121

14

120

14 ωωωω ppp +=

)()()( 021

24

020

24 ωωωω ppp +=

)()()( 121

34

120

34 ωωωω ppp +=

23

Berechnung von DFTn

Einfachster Fall: n = 1 (Grad(p) = n –1 = 0)DFT1(p) = a0

Sonst : Divide:Teile p in p0 und p1 aufConquer:Berechne DFTn/2(p0) und DFTn/2(p1) rekursivMerge:Berechne für k = 0, ... , n –1:

DFTn(p)k =

( ) ( ) ( )( )110 ,,,)( −= n

nnnn ppppDFT ωωω K

knnkn

knn

pDFTpDFTpDFTpDFT

))(),(())(),((

12/12/

02/02/

⋅

+

ω

24

Eine kleine Verbesserung

Also falls k < n/2:( ) ( ) ( )k

nkn

kn

kn ppp ωωωω =+ 2/12/0

( ) ( ) ( )2/2/12/0

nkn

kn

kn

kn ppp +=− ωωωω

( )

( ) ( )

( ) ( )⎪⎪⎩

⎪⎪⎨

⎧

≥+<

+

=−−

2/ falls

2/ falls,

2/2/1

2/2/0

2/12/0

nkppnkpp

pnk

nkn

nkn

kn

kn

kn

kn ωωω

ωωω

ω

( ) ( )

( ) ( )⎪⎪⎩

⎪⎪⎨

⎧

≥−

<+

=−−−

2/ falls,

2/ falls,

2/2/1

2/2/2/0

2/12/0

nkpp

nkpp

nkn

nkn

nkn

kn

kn

kn

ωωω

ωωω

25

Eine kleine Verbesserung

Beispiel:

)()()( 021

04

020

04 ωωωω ppp +=

)()()( 121

14

120

14 ωωωω ppp +=

)()()( 021

04

020

24 ωωωω ppp −=

)()()( 121

14

120

34 ωωωω ppp −=

26

6. Fast Fourier TransformationAlgorithmus 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 a3. d[0] = FFT([a0, a2, ... , an-2 ], n/2)4. d[1] = FFT([a1, a3, ... , an-1], n/2)5. ωn = e2πi/n

6. ω = 17. for k = 0 to n/2 – 1 do /* ω = ωn

k*/8.9.10.11.return d

[ ] [ ]

[ ] [ ]

ωωωω

ω

n

102/

10

⋅=⋅−=

⋅+=

+ kknk

kkk

ddd

ddd

27

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 ; ω = 1d0 = -15 + 1 * 21 = 6 d2 = -15 – 1 * 21 = -36

k = 1 ; ω = id1 = 15 + i*15 d3 = 15 – i*15

FFT(a, 4) = (6, 15+15i, -36, 15 –15i)

( ) 018153 23 ++−= xxxxp

28

7. Analyse

T(n) = Zeit um ein Polynom vom Grad < n an den Stellenauszuwerten.

T(1) = O(1)T(n) = 2 T(n/2) + O(n)

= O(n log n)

122

12

02 ,,, −n

nnn ωωω K

29

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 ωωω K

( )( )in

in p 22 , ωω ( )( )i

nin q 22 , ωω

( )( )in

in pq 22 , ωω

30

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

( )( )( )

( ) 11111101

21

212102

11

111101

01

010100

−

−

−−−−

−

−

−

−

−

−

=+++=

=+++==+++==+++=

nnnnnn

nn

nn

nn

yxaxaaxp

yxaxaaxpyxaxaaxpyxaxaaxp

KMM

KKK

31

Matrixschreibweise

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−−

−

−−

−

−

1

1

0

1

1

0

111

121

100

1

11

nnnnn

n

n

y

yy

a

aa

xx

xxxx

MM

L

M

L

L

Interpolation

32

Interpolation

Spezialfall (hier) :

Definition:

jixxy

yy

a

aa

xx

xxxx

ji

nnnnn

n

n

≠≠

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−−−−−

−

−

allefür ,für lösbar ist 1

11

systemGleichungs

1

1

0

1

1

0

111

111

100

MM

L

M

L

L

( ) ( ) ( )

V

, ,

1n

,

yVaya

yyaaV

n

iiji

ijnn

−=⇒=

=== ω

inix ω=

33

Interpolation

SatzFür alle 0 ≤ i, j ≤ n – 1 gilt:

( )n

Vij

nijn

−− =

ω1

Beweis

ji

ijn

n nV

,

1⎟⎟⎠

⎞⎜⎜⎝

⎛=

−− ω

zu zeigen:

nnn IVV =−1

34

Interpolation

( )

ijjn

n

jn

jn

nin

in

ijnn

nn

nnn

VVjiVV

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=

−

−−−

−

−

LL

M

LL

LL

LL

L

M

L

L

)1(

2

)1(

1

1

1

1

: Spalte , in Zeile von Eintrag Betrachte

ω

ωωωω

35

Interpolation

( ) ∑∑−

=

+−−

=

−− ==

1

0

)(1

0

1 1 n

k

kjin

n

k

jkn

ikn

ijnn nnVV ωωω

Fall 1: i = j

( ) ∑∑−

=

⋅−

=

+− ==1

0

01

0111 n

k

kn

n

k

kjin nn

ωω

Fall 2: i ≠ j, ( ): | damit

und 11 d.h. jin

njin+−/

−≤+−≤−−

( )∑−

=

+− =1

001 n

k

kjinn

ω

36

Interpolation

SummationslemmaFür alle n > 0, l ≥ 0 mit n l

Beweis: 0

1

0=∑

−

=

n

k

lknω

( ) ( ) ( ) 011

111

0=

−−

=−−

=∑−

=ln

lnn

ln

nln

n

k

kln ω

ωωωω

37

Interpolation

( )

( )

( )∑

∑

−

=

−

−

=

−

−

−−−

−

=

=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎠

⎞⎜⎜⎝

⎛=

=

1

0

1

0

1

1

01

1

1

,,,1

n

k

kink

n

k

ikn

k

n

nin

in

ini

yn

ny

y

yy

nnn

yVa

ω

ω

ωωM

K

38

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

ωωω

ωωω

K

L

L

39

Interpolation und DFT

( ) ( )0 )(1 ≠= − irDFTn

a inni

( ) ( ) ( )( ))1(10 ,,,1 −−−−= n

nnn rrrn

a ωωω K

( ) ( ) ( )( )11 ,,,1n

nn

nn rrr

na ωωω K−= 1=n

nωdenndenn

( ) )(1 00 rDFTn

a n=

40

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 ωωω K

( )( )in

in p 22 , ωω ( )( )i

nin q 22 , ωω

( )( )in

in pq 22 , ωω