Einführung in die Programmierung (MA8003)Theorie 3.2: Effiziente Behandlung dünnbesetzter Systeme

Dr. Lorenz John

Technische Universität MünchenFakultät Mathematik, Lehrstuhl für Numerische Mathematik M2

06.10.2016

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Theorie 3.2: Inhalt

1 Dünnbesetzte MatrizenMotivationSpeichermodellBeispieleErzeugen von Sparse-MatrizenVergleich voll- und dünnbesetztErhalten dünn besetzter Strukturen

2 Beispiel: Kubische Splines

3 Nützliche WerkzeugeProfilerMLINTDependency Report

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

MotivationFür viele Probleme (z.B. bei der Diskretisierung partiellerDifferentialgleichungen, Bestimmung von Koeffizienten bei derInterpolation) erhält man Matrizen, die viele Nullen enthalten.Beispiel: Poissonmatrix

A =

4 −1 0 −1 0 0 0 0 0

−1 4 −1 0 −1 0 0 0 0

0 −1 4 0 0 −1 0 0 0

−1 0 0 4 −1 0 −1 0 0

0 −1 0 −1 4 −1 0 −1 0

0 0 −1 0 −1 4 0 0 −1

0 0 0 −1 0 0 4 −1 0

0 0 0 0 −1 0 −1 4 −1

0 0 0 0 0 −1 0 −1 4

Speicherplatz sparen: nur Nicht-Null-Einträge abspeichernEffizientes Rechnen: Operation mit Null-Einträgen vermeiden

Durch diese Effizienzsteigerungen können Probleme berechnet werden,die ansonsten aufgrund ihrer Größe nicht verarbeitet werden könnten.

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Speichermodell von Sparse-Matrizen

Nur von Null verschiedene Einträge werden abgespeichertDer Ort des Eintrags wird durch den Zeilen- und SpaltenindexgekennzeichnetSpeicherplatzbedarf ist ungefähr gleich der Summe von

4 Bytes, um die Anzahl der Einträge zu speichernpro Eintrag 8 Bytes für Spalten- und Zeilenindexpro Eintrag 8 Bytes für den Zahlenwert

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Beispiele für Sparse-Matrizen

A =

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

A =

(1,1) 1(2,2) 1(3,3) 1(4,4) 1

B =

2 −1 0 0 0

−1 2 −1 0 0

0 −1 2 −1 0

0 0 −1 2 −1

0 0 0 −1 2

B =

(1,1) 2(2,1) -1(1,2) -1(2,2) 2(3,2) -1(2,3) -1...

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Befehle zum Erzeugen von Sparse-Matrizen

Funktion Beschreibungspeye Schwach besetzte Einheitsmatrixspones Einträge durch Einsen ersetzenspdiags Erzeugen von Bandmatrizensprand Einträge durch Zufallszahlen ersetzen

Konvertierung von A nach schwach bzw. voll besetzt:full(A)

sparse(A)

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Beispiel: spdiags

>> n = 5; e = ones(n,1); d = 4*e;>> A = spdiags([-e, d, -e], [-1,0,1], n, n);>> full(A)ans =

4 -1 0 0 0-1 4 -1 0 00 -1 4 -1 00 0 -1 4 -10 0 0 -1 4

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Vergleich Speicherplatzbedarf

0 2 4 6 8 10 12 14 16 18 200

500

1000

1500

2000

2500

3000

3500

n: Dimension der n x n Matrix

Spe

iche

rpla

tzbe

darf

in B

ytes

Speicherplatzbedarf einer Tridiagonalmatrix

schwach besetztvoll besetzt

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Vergleich Rechengeschwindigkeit

0 20 40 60 80 100 120 140 160 180 2000

0.002

0.004

0.006

0.008

0.01

0.012

n: Dimension der n x n Matrix

gem

esse

ne G

esch

win

digk

eit a

uf P

4 in

[s]

Geschwindigkeit Lösen eines Tridiagonalsystems mit \

schwach besetztvoll besetzt

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Erhalten dünn besetzter StrukturenIn der Regel ist die Inverse einer dünn besetzten Matrix nicht mehrdünn besetzt.Daher: Oft besser, Inverse nicht explizit zu bestimmen. Stattdessenkann man oft ein lineares Gleichungssystem (z.B. mit dem \Operator) lösen.Beispiel: Matrixstruktur CSOR = D + L für Poisson-Matrix

0 10 20 30 40 50 60 70 80 90 100

0

10

20

30

40

50

60

70

80

90

100

nz = 280

CSOR

(ω = 1)

0 10 20 30 40 50 60 70 80 90 100

0

10

20

30

40

50

60

70

80

90

100

nz = 3025

C−1SOR

(ω = 1)

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

InterpolationsaufgabeGegeben: Paare (xi , yi) ∈ R× R, i = 0, . . . , n mit x0 < x1 < . . . < xnder zu interpolierenden Werten.Gesucht: Funktion S : R→ R mit S(xi) = yi , i = 0, . . . , n, aus einemvorgegebenen Funktionenraum, z.B. zweimal stetig differenzierbar.

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Kubische Splineinterpolation

Idee: Stelle Funktion S auf jedem Teilintervall [xi , xi+1] als kubischesPolynom dar:

Pi(x) = αi + βi(x − xi) + γi(x − xi)2 + δi(x − xi)3.

Wähle die Koeffizienten (αi , βi , γi , δi) so, dass Interpolationsaufgabegelöst wird und gesamte Funktion S zweimal stetig differenzierbar ist.

MomentenmethodeMomente: Mi = S ′′(xi) = P ′′i (xi) = P ′′i−1(xi)Koeffizienten (hi+1 = xi+1 − xi):

αi = yi , βi = yi+1 − yihi+1

− 2Mi + Mi+16 hi+1

γi = Mi2 δi = Mi+1 −Mi

6hi+1

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Berechnung der MomenteDie Momente M sind Lösung des linearen Gleichungssystems

2 λ0µ1 2 λ1

µ2 2 λ2. . . . . . . . .

µn−1 2 λn−1µn 2

M0M1...

Mn−1Mn

=

d0d1...

dn−1dn

(1)

mit (j = 1, . . . , n − 1)

λj = hjhj + hj−1

µj = 1− λj

dj = 6hj + hj−1

(yj+1 − yj

hj− yj − yj−1

hj−1

).

Für den natürlichen Spline setzt man noch

λ0 = d0 = dn = µn = 0.

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Matlab Code

function [ P ] = kspline( x, y )n = length(x);jj = 1:n-1; j = 2:n-1;h = [x(jj+1)-x(jj)];lambda = [0, h(j+1)./(h(j)+h(j+1))];mu = [1-lambda(j), 0];d = [0, (6./(h(j)+h(j+1))).*((y(j+1)-y(j))./h(j+1) ...

- (y(j)-y(j-1))./h(j)), 0];A = 2*eye(n) + diag(lambda, 1) + diag(mu, -1);M = (A \ d’)’;alpha = y(jj); gamma = M(jj)/2;beta = (y(jj+1)-y(jj))./h(jj+1) - h(jj+1).*(2*M(jj)+M(jj+1))/6;delta = (M(jj+1)-M(jj))./(6*h(jj+1));P = [alpha’, beta’, gamma’, delta’];

end

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Matlab Code

Aus dicht mach dünn!function [ P ] = kspline( x, y )

n = length(x);jj = 1:n-1; j = 2:n-1;h = [x(jj+1)-x(jj)];lambda = [0, h(j+1)./(h(j)+h(j+1))];mu = [1-lambda(j), 0];d = [0, (6./(h(j)+h(j+1))).*((y(j+1)-y(j))./h(j+1) ...

- (y(j)-y(j-1))./h(j)), 0];A = 2*speye(n) + spdiags([[lambda, 0]’, [mu, 0]’], [1, -1], n, n);M = (A \ d’)’;alpha = y(jj); gamma = M(jj)/2;beta = (y(jj+1)-y(jj))./h(jj+1) - h(jj+1).*(2*M(jj)+M(jj+1))/6;delta = (M(jj+1)-M(jj))./(6*h(jj+1));P = [alpha’, beta’, gamma’, delta’];

end

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Laufzeiten

A vollbesetzt

n Zeit (1000 Ausführungen) Speicher100 0.79sec 93kB200 2.57sec 342kB400 32.00sec 1309kB800 138.00sec 5118kB1600 570.00sec 20237kB

A dünnbesetzt

n Zeit (A dünn) Speicher (A dünn)100 0.87sec 17kB200 1.33sec 34kB400 2.44sec 68kB800 4.85sec 137kB

1600 9.64sec 275kB

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Profiler

Detaillierte Rechenzeitanalyse: Wieviel Zeit wurde für welche Zeileoder Funktion verbraucht?Auflistung geordnet nach RelevanzGut geeignet zum Auffinden von EffizienzproblemenFalls optimiert werden soll, wo wäre Optimierung sinnvoll?Vorgehen:

1 Profile Aufzeichnung starten mit profile on2 m-File aufrufen3 Profile report ansehen mit profile viewer.4 Optionen: Abspeichern von Berichten, Detail-Level setzen (z.B.

interne Funktionen in Laufzeitmessung einschließen), . . .

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Beispiel: Profiler, Zusammenfassung

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Beispiel: Profiler, Details

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

MLINT Code Checker

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Dependency Report

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)

Fragen?

Ende Theorie 3.2

Fragen?

Numerische Mathematik M2 z.T. basierend auf Boris von Loesch Einführung in die Programmierung (MA8003)