Lösung linearer Gleichungssysteme Seminar Parallele Programmierung Nico Ziborius

Lösung linearer Gleichungssysteme

Seminar “Parallele Programmierung“

Nico Ziborius

2

Gliederung

1. Einleitung

2. Direkte Verfahren

2.1 Gauß-Elimination

2.2 zyklische Reduktion

3. Iterative Verfahren

3.2 Methode der konjugierte Gradienten

3.1.2 Gauß-Seidel-Verfahren

3.1.1 Jacobi-Verfahren

3.1 klassische iterative Verfahren

4. Zusammenfassung

3

Gliederung

1. Einleitung









4. Zusammenfassung

4

1. Einleitung

• linearer Gleichungssysteme Kern vieler numerischer Anwendungen (z.B numerische Lösung partieller Differentialgleichungen)

• Gesucht Lösung für Ax =b– nichtsinguläre Matrix ARnn

– Vektor bRn und Lösungsvektor xRn

• Direkte-Verfahren– exakte Lösung– z.B. Gauß-Elimination, zyklische Reduktion

• Iterative-Verfahren– Näherung an die Lösung – z.B. Jacobi-Verfahren, Gauß-Seidel-Verfahren, Methode der

konjugierten Gradienten

5

Gliederung

1. Einleitung









4. Zusammenfassung

6


Idee:

• Transformiere Ax=b in äquivalentes Gleichungssystem A‘x = b‘, so dass A‘ eine obere Dreiecksmatrix bildet.

7

nikfür )(

)(

aal k

kk

k

ikik

alaak

kjik

k

ij

k

ij

)()()1(*

blbbk

kik

k

i

k

i

)()()1(*

2.1 Gauß-Elimination• Transformation benötigt n-1 Schritte

– Elemente von A und b für k< j n und k <i n neu berechnen:

– Eliminationsfaktoren berechnen:

aa

aaaaa

aaaaaaaaa

k

nn

k

nk

k

kn

k

kk

k

nk

k

kk

k

kk

nkk

nkk

k

)()(

)()(

)1(

,1

)1(

,1

)1(

1,1

)2(

2

)2(

2

)2(

1,2

)2(

22

111,11211

)(

00

0

0

A

• Schritt k , 1 k n-1

• A(k+1), b(k+1) aus A(k), b (k) berechnen:

8


• Lösung durch Rückwärtseinsetzen, für k = n,n-1,...,1:

n

kj

n

kj

n

kn

kk

k aba 1

j

)()(

)( xx1

• sequentielle Implementierung Θ(n3)

(drei ineinander verschachtelte Schleifen)

9


• Elemente auf der Diagonalen gleich Null Fehler, da Division durch Null

• sehr kleine Elemente auf der Diagonalen Rundungsfehler

• daher Elemente auf der Diagonalen durch ein andere, sogenannte Pivotelemente, ersetzten: – Spaltenpivotsuche:

– betragsgrößte ark(k) aus akk

(k),..,ank(k) suchen

– vertauschen der Zeilen k und r , falls r k.

10


• zeilenblockweise Aufteilung der Matrix A und des Vektor b

• mit p = Anzahl Prozessoren, wird Pi für 1 i p, ein n/p großer Zeilenblock zugewiesen

• Jeder Prozessor Pi hat

– ein 2-dimensionales Array a[n/p][n] (Koeffizienten Matrix A)

– Array b[n/p] (Werten des Vektors b)– Array marked[n/p] (markieren der Pivotzeile)– Array pivot[n/p], (wann war Zeile Pivotzeile)

parallelen Implementierung: (Hypercube)

11

• zunächst Array marked mit 0 initialisieren

• dann in n-1 Schritten die obere Dreiecksmatrix berechnen:

1. lokales Pivotelement bestimmen:

Pi ermittelt unter den Elementen a[r][k], mit r= 1...n/p und marked[r]=0 das lokale Maximum


a

1

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

0

0

1

-

-

-P2

P1

b marked pivot

1

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

0

0

1

-

-

-P2

P1

b

12

2. globales Pivotelement bestimmen: Aus den lokalen Maxima wird das globale Maximum, durch Auruf der Funktion

MAX_TOURNAMENT(int i, int value, int winner) ermittelt


int MAX_TOURNAMENT(int i, int value, int winner){int j,k;for(k=0; k<log p-1; k++){

j=i^(1<<k);[j]tmp_value value;[j]tmp_winner winner;if(tmp_value>value){

value = tmp_value; winner = tmp_winner;}

}return winner;}

13

1

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

0

0

1

-

-

-P2

P11

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

1

0

1

-

2

-P2

P13. Pivotzeile Markieren &

Verteilen: wenn Pi Gewinner, dann marked[r]=1, pivot[r]=k, Elemente a[r][k]... a[r][n] und b[r] in Hilfsvektor kopieren und an alle andere Prozessoren senden


4. Berechnung der Eliminationsfaktoren: Pi berechnet für seine lokalen Zeilen i, mit i =1,...n/p, mit marked[i]=0, die Eliminationsfaktoren

marked pivotba

1

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

0

0

1

-

-

-P2

P11

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

1

0

1

-

2

-P2

P1

1

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

0

0

1

-

-

-P2

P11

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

1

0

1

-

2

-P2

P1

14


5. Neu Berechnung Matrixelemente: Pi berechnet seine Elemente a[i][j], und b[i], i=1...n/p, j=k+1...n, mit marked[i]=0, neu.

• jeder Prozessor sucht in seinem Array marked nach marked[j]=0 und setzt pivot[j]=n

• Lösung des Gleichungssystems durch Rückwärtseinsetzten

1

0

0

0

2

4

-8

-1

3

4

-2

-5

-4

-1

10

11

-6

14

3

7

1

0

0

0

1

-

-

-P2

P11

0

0

0

2

0

-8

0

3

5

-2

-4,75

-4

4

10

9,75

-6

15,5

3

6,625

1

0

1

0

1

-

2

-P2

P1

marked pivotba

15


.)()(),(1

11

n

ip

nin

p

nin

p

n

p

npnt

2

3

1 ),( np

npnt

Berechnungsaufwand:

Kommunikationsaufwand:

,loglog)(log),(1

12

n

i

ppinppnt

pnpnn

pinppntn

i

loglog2

)1(log)(1log),( 2

1

12

Initialisierung marked Pivotzeile ermitteln

Pivotzeile kopieren

Eliminationsfaktoren & Elemente von A, b neu berechnen

pivot

16


• Vorteile:

– Vorhersagbarkeit der Laufzeit, des Speicherbedarfs

– Berechnung einer exakten Lösung

• Nacheilt:

– bei dünnbesetzten Matrizen entsteht fill-in

17

Gliederung

1. Einleitung









4. Zusammenfassung

18


• Eine Matrix A mit A= (aji) i,j=1,...,n Rnn heißt Bandmatrix mit halber Bandbreite r, falls aij = 0 für |i-j| >r.

• Falls r = 1 , so heißt A Tridiagonalmatrix

nn

n

ba

c

ba

cba

cb

A

0

0

1

33

222

11

• Gauß-Elimination hier nicht Sinnvoll!

19


• Falls A symmetrisch und positiv definit Lösung mittels– rekursiven Verdoppelns oder zyklischer Reduktion

• Ausgangspunkt beider Verfahren:

nn

iiii

yb

ifürycba

ycb

x xa

1-n,2, x x x

xx

n 1-nn

1ii1-i

12111

Idee:

• xi-1 und xi+1 aus der i-ten Gleichung, durch einsetzen von geeigneten Vielfachen der Gleichungen i+1 und i-1, zu eliminieren

20


• Nach log n Schritten, nur noch Elemente der Hauptdiagonalen ungleich Null

Lösung ist einfach abzulesen

nn

n

ba

c

ba

cb

cb

A

00

0

0

00

00

)1(

)1(2

3)1(

3

)1(2

)1(2

)1(1

)1(1

)1(

• Pro Schritt werden O(n) Werte berechnet: O(nlog n) gegenüber O(n) für Gauß-Elimination

aber Berechnung der Werte innerhalb eines Schrittes parallel möglich

21


zyklische Reduktion :

• die Zahl der berechneten Werte in jedem Schritt halbiert

• erfordert abschließende Substitutionsphase

rekursives Verdoppeln :• Diagonalmatrix in log n Schritten ermitteln

22


parallele Implementierung:

• Zeilen der Tridiagonalmatrix A blockweise auf p Prozessoren aufgeteilen

• Zur Vereinfachung:

– n = pq mit q

– q = 2Q mit Q N

– Pi speichert Zeilenblock der Größe q, mit den Zeilen (i-1)q+1,...,i*q, für 1 i p

23


parallele Implementierung:

1. zyklische Reduktion: bis nur noch eine Gleichung pro Prozessor vorhanden

log p Stufen

x4

x8

2. rekursives Verdoppeln: das nur noch p-dimensionale Gleichungssystem wird nun mittels rekursiven Verdoppeln in gelöst

3. Substitutionsphase: Ermittlung der noch fehlenden

Werte des Lösungsvektors x

Q Stufen

x6

x2

x7

x3

x5

x1

Q Stufen

24


• Aufwand Phase 1:

op

Q

kkop t

p

nqtpnT

162

44),(

11

)4(log2)4(2),( 221 ssss tp

ntQpnC


opopopop ttptptpnT log16log44),(2

)4(log2),( 22 sstppnC


15)1(5)12(525),(1

03 p

ntqtttpnT opop

Qop

Q

k

kop

)1(2),( 23 sstpnC

25


• Aufwand Insgesamt:

optp

np

p

npnT

45log1616),(

optpp

n

log1621

)1(2loglog2),( 2sstpp

npnC

)1(2)4(log2 22 ssss ttn

26

Gliederung

1. Einleitung









4. Zusammenfassung

27


• Berechnen Folge von Approximationsvektoren {x(k)}k=1,2,...,,

die gegen die gesuchte Lösung x*Rn konvergieren

• Zerlegung der Matrix A in A=M-N mit M,N Rnn

– M nichtsinguläre Matrix

– M-1 leicht zu berechnen, z.B. Diagonalmatrix

• x* erfüllt Gleichung: Mx* = Nx* +b.

Iterationsvorschrift: Mx(k+1) = Nx(k) + b

28

Gliederung

1. Einleitung









4. Zusammenfassung

29


• Zerlegung von A in A=D-L-R mit (D,L,R Rnn), – D Diagonalmatrix, L untere Dreiecksmatrix, R obere

Dreiecksmatrix (jeweils ohne Diagonale)

• Iterationsvorschrift: Dx(k+1) =(L+R)x(k) + b

n, 1,...i , 1

,1

)()1(

n

ijj

kjiji

ii

ki xab

ax

• In Komponentenschreibweise:

30


• Abbruchkriterium: relativer Fehler

)1()()1( kkk xxx

||.|| Vektornorm, z.B. ||x|| = max i=1,...,n|xi| oder ||x||2=(n i=1|x|2)½ .

31


parallel Implementierung:

• Pi mit i=1,...,p speichert die Werte xi(n/p),..., x(i+1)(n/p)-1 inklusive

dazugehörige Zeilen von A und der Werte von b • jeder Pi führt nun alternierend folgende Aktionen aus, bis

Abbruchkriterium erfüllt:1. Pi sendet seine lokal gehaltenen Elemente des Vektors x(k) an

alle anderen Prozessoren (All-to-All Broadcast)

2. Pi berechnet x(k+1) für seine Elemente xj(k+1) mit j=i(n/p),...,(i+1)

(n/p)-1

3. Test des Abbruchkriterium

32

3.1.1 Jacobi-Verfahren• Aufwand :

– In Schritt 1. sendet Pi n/p Werte an p-1 Prozessoren Kommunikationsaufwand Θ((p-1) (n/p)).

– In Schritt 2. n/p Elemente des Vektors x(k+1) berechnen, mit Rechenaufwand von Θ(n (n/p))

– Der Test auf Abbruch in 3. erfordert einen Aufwand von Θ (log p).

• Bewertung:– Konvergenz nicht gesichert , niedrige Konvergenzrate

• es gezeigt, dass e(n2/2) Iterationen notwendig sind damit der Fehler um 10-e sinkt

• Für n= 64 wären ca. 3(642/2)= 6144 Iterationen notwendig um den Fehler um 10-3 zu reduzieren

– kein fill-in, geringer Speicherbedarf bei dünnbesetzten Matrizen

33

Gliederung

1. Einleitung









4. Zusammenfassung

34


• Zerlegung der Matrix A anlog zum Jacobi-Verfahren, A=D-L-R (D,L,R Rnn)

• Iterationsschritt: (D-L)x(k+1)=Rx(k)+b.

• in Komponentenschreibweise

n,1,i, 1 1

1

)(

1

)1()1(

i

j

kj

n

ijij

kjiji

ii

ki xaxab

ax

35


• Einbeziehung der neu Berechneten Approximation deutlich verbesserte Konvergenzrate Konvergenzrate: n(e/3) Iterationen um den Fehler um den

Faktor 10-e zu senken aber Datenabhängigkeiten, die eine Parallelisierung des

Verfahrens erschweren

n,1,i, 1 1

1

)(

1

)1()1(

i

j

kj

n

ijij

kjiji

ii

ki xaxab

ax

36


• In Dünnbesetzte Matrizen weniger Datenabhängigkeiten

• Eine Möglichkeit Rot-Schwarz-Anordnung, für Gleichungssysteme, die von einer Gitterstruktur herrühren

xi,j= (xi-1,j + xi+1,j + xi,j-i + x i,j+1) / 4

• Bsp. Temperaturverlauf im Wasserbad

37


xxx

xxxx

xxx

xxx

xxxx

xxxxx

xxxxx

xxxx

xxxx

xxxxx

xxxxx

xxxx

xxx

xxxx

xxxx

xxx

• Für n = 16 Punkte ergibt sich folgendes Gitter und Matrix A

1

5

9

2

6

10

13 14

3

7

11

15

4

8

12

16

38

1

5

9

2

6

10

13 14

3

7

11

15

4

8

12

16


• Rote-Schwarz-Anordnung : 1

5

3

7

2

6

4

8

1

11

5

9

3

13

15 7

2

12

6

16

10

4

14

8

– rot Punkt nur schwarze Nachbarn und umgekehrt

– Die Rote von 1,...,nS, numerieren

– die Schwarze von nS+1,... ,nR+nS numerieren (nR+nS=n)

xxxx

xxx

xxxx

xxxxx

xxxx

xxxx

xxx

xxxx

xxx

xxxx

xxxxx

xxxx

xxxx

xxxxx

xxxx

xxx

S

R

D0

0DD

0E-

00L

00

F-0R

• neue Matrix Â (Permutation von A)

• Die Zerlegung von Â in Â =D-L-R (D,L,R Rnn) mit

39


• Iterationsschritt:

1)(kR2

1)(kSS

(k)S1

1)(kRR

ˆD

FˆD

xEbx

xbx

R)(

)1(,

,

)1(

S)(

)()1(

n, 1,...i , ˆˆ

1

,n, 1,...i , ˆˆ1

n

iNjj

kRjnini

ninii

kS

iNjj

kSiji

iii

kR

xaba

x

xaba

x

ss

ss

• in Komponentenschreibweise:

2

1

S

R

S

R

ˆ

ˆ

x

ˆ.

DE

FDˆA

b

bxx

40


• maximal p=nr (bzw. p=ns) Prozessoren

• Aufteilung anhand des Gitters vorgenommen

– wird Pj Gitterpunkt i zugeordnet, dann Pj für Berechnung der

Approximationen von xi zuständig

– Aufteilung z.B. zeilenblockweise

– bei p Prozessoren erhält jeder Prozessor n / p Gitterzeilen (½(n / p) rote und schwarze Punkte)

parallel Implementierung:

41


• wähle beliebigen Startvektor

• Prozessoren iterieren folgende Schritte bis der Test auf Abbruch erfolgreich

1. Pi sendet seine lokal Elemente von xS(k) an alle anderen

Prozessoren (All-to-All Broadcast)

2. Pi berechnet die neue Approximation xR(k+1) für seine Elemente

von xR(k)

3. Pi sendet seine Elemente von xR(k+1) an alle anderen

Prozessoren (All-to-All Broadcast)

4. Pi berechnet die neue Approximation xS(k+1) für seine Elemente

von xS(k)

5. Test auf Abbruch

42


• Der Rechenaufwand fast identisch zu dem des Jacodi-Verfahrens

– In Schritt 2 und 4 jeweils n/2p Elemente der neuen Approximation berechnen,

insgesamt die gleiche Anzahl, wie beim Jacobi-Verfahrens

• eine All-to-All Broadcastoperation mehr erforderlich (Schritt 1 und 3)

• zusätzlicher Aufwand durch verbessertes

Konvergenzverhalten kompensiert

Aufwand:

43

Gliederung

1. Einleitung









4. Zusammenfassung

44

3.2 Methode der konjugierten Gradienten

• Voraussetzung: Matrix ARnn positiv definit und symmetrisch

• Lösung x* des Gleichungssystems entspricht dem Minimum der Funktion:

xbAxxxf TT 2

1)(

• f(x) ist konvex und besitzt eindeutiges Minimum x*

45


• Iterationsschritt:)()()1( )( kkk pkxx

(k) Schrittweite , p(k) Richtungsänderung

– Notwendige Bedingung, mit r = Ax-b :

App

rp

App

bAxpbAxpApp

da

pxdfT

T

T

TTT

)(

0)()(

min

– Hinreichende Bedingung:

0)(

2

2

Appda

pxdf T

• Bestimmung von (k) bei bekanntem p(k) :

immer erfüllt !

)((min))(( )()()( kkR

k pxfpkxf

46


• Wahl des Richtungsvektors p(k) :– die Richtungsvektoren p(k) sind so zu wählen, dass sie konjugierte

Basis des Rn bzgl. A bilden:

• Zwei Vektoren p,q Rn sind bzgl. einer symmetrischen, nicht singulären Matrix A konjugiert falls gilt qTAp=0.

• Ist A positiv definit so bilden die linear unabhängigen Vektoren p1,...,pn, mit pi 0, i=1,...,n und (pi)TApj=0 für alle i,j

eine konjugierte Basis des Rn bzgl. A. – Falls die Richtungsvektoren eine konjugierte Basis des Rn bzgl. A

bilden, dann liegt die exakte Lösung nach maximal n Schritten vor.

47


Der Algorithmus:

– Initialisierung: wähle Startvektor x(0) und setzte p(0) =-r(0) =b-Ax(0)

sowie k=0

– Iteration: solange ||r(k)||> berechne

1. q(k) =Ap(k)

2. k = [(r(k))T r(k)] / [ (p(k))T q(k) ]

3. x(k+1) =x(k) + kp(k)

4. r(k+1) =r(k) + kq(k)

5. k= [(r(k+1))T r(k+1)]/ [(r(k))T r(k)]

6. p(k+1) =-r(k+1)+ kp(k)

7. k++

Basisoperationen:

Matrix-Vektor-Multiplikation

ein inneres Produkt

eine Vektor-Addition


ein inneres Produkt


48


parallele Implementierung: zeilenblockweise Aufteilung von A und

blockweise Aufteilung der Vektoren durch Parallelisierung der verwendeten

Basisoperationen

• eine Matrix-Vektor-Multiplikation

• zwei innere Produkte

• drei Vektor-Additionen

p

nTsaxpy

p

p

nTip log

)()(2

p

nnn

p

np

p

nTMVM

49


Rechenaufwand:

pnp

n

p

n

p

np

p

n

p

nnTTTT saxpyipMVMCG

log5

3log232

2

2

50

Gliederung

1. Einleitung









4. Zusammenfassung

51

4. Zusammenfassung

• Das Gauß-Eliminations-Verfahren– exakte Lösung – Vorhersagbare Rechenzeit – auf fast alle linearen Gleichungssystem Anwendbar– Nachteil fill-in

nur für fast voll besetze Matrizen geeignet

• zyklische Reduktion

– für Matrizen mit spezieller Struktur– exakte Lösung – Vorhersagbare Rechenzeit

52

4. Zusammenfassung

• Iterative Verfahren

– kein fill-in

– Rechenzeit nicht Vorhersagbar

– für dünnbesetze Matrizen geeignet

– GS-Verfahren konvergiert schneller als das Jacobi-Verfahren, aber Datenabhängigkeiten

– bei symmetrischer, positiv definiter Koeffizientenmatrix Methode der konjugierten Gradienten

• exakte Lösung bei rundungsfehlerfreier Rechnung nach höchstens n Schritten

53

Vielen Dank für die Aufmerksamkeit!

Documents

Lösung linearer Gleichungssysteme Seminar Parallele Programmierung Nico Ziborius