WS 2006-07

Algorithmentheorie

02 - Polynomprodukt undFast Fourier Transformation

Prof. Dr. Th. Ottmann

2WS 2006-07

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 2006-07

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 2006-07

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 2006-07

Operationen auf Polynomen

3. Auswerten an der Stelle x0: Horner-Schema

Zeit: O(n)

0010100

axaxaxaxpnn

6WS 2006-07

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 2006-07

Repräsentation eines Polynoms

2. Nullstellenprodukt

p(x) R[x]

Beispiel:

nn

xxxxaxp 1

323 xxxxp

8WS 2006-07

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 2006-07

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 2006-07

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 2006-07

Polynomprodukt

Berechnung des Produkts zweier Polynome p, q vom Grade < n

p,q Grad n-1, n Koeffizienten

Auswertung:

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 2006-07

Ansatz für Divide and Conquer

Idee: (n sei gerade)

21

20

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 2006-07

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 2006-07

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 2006-07

Auswertung an den Einheitswurzeln

i1

4

10

412

4

i3

4

16WS 2006-07

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

xxxxp 18153 23

17WS 2006-07

Polynomprodukt

Berechnung des Produkts zweier Polynome p, q vom Grade < n

p,q Grad n-1, n Koeffizienten

Auswertung:

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 2006-07

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 2006-07

5. Diskrete Fourier Transformation

Fast Fourier Transformation:

Berechnung von DFTn(p) mittels

eines Divide-and-Conquer Ansatzes

110 ,,,)( n

nnnnppppDFT

20WS 2006-07

Diskrete Fourier Transformation

Idee: (n sei gerade)

2/2

1311

2/2

2200

n

n

n

n

xaxaaxp

xaxaaxp

21

20

2/221

231

2/222

220

11

331

22

220

1110

xxpxp

xaxaax

xaxaa

xaxaxa

xaxaa

xaxaaxp

n

n

n

n

nn

nn

nn

21WS 2006-07

Diskrete Fourier Transformation

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

21

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

22WS 2006-07

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

23WS 2006-07

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/

24WS 2006-07

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

25WS 2006-07

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

26WS 2006-07

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*/

8.9.10.11. return d

n

102/

10

kknk

kkk

ddd

ddd

27WS 2006-07

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 –15i)

018153 23 xxxxp

28WS 2006-07

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

29WS 2006-07

Polynomprodukt

Berechnung des Produkts zweier Polynome p, q vom Grade < n

p,q Grad n-1, n Koeffizienten

Auswertung 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 ,

30WS 2006-07

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

31WS 2006-07

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

32WS 2006-07

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

33WS 2006-07

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

34WS 2006-07

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

35WS 2006-07

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

36WS 2006-07

Interpolation

Summationslemma

Für alle n > 0, l 0 mit n l

Beweis: 0

1

0

n

k

lkn

0

1

1

1

11

0

ln

lnn

ln

nln

n

k

kln

37WS 2006-07

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

38WS 2006-07

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

39WS 2006-07

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

40WS 2006-07

Polynomprodukt durch FFT

Berechnung des Produkts zweier Polynome p, q vom Grade < n

p,q Grad n-1, n Koeffizienten

Auswertung 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 ,