Anlaufschwierigkeiten starten wir nun die Vorlesung.

So, wo sind wir letzte Woche angekommen?

Also, bzw. wir fangen jetzt erstmal an mit Gleichungslösern in der CE2.

Und wir haben letzte Woche begonnen mit, vielleicht nochmal zum Überblick,

also erstmal mit der Rücksubstitution, wenn wir eine Matrix gegeben haben,

die folgendermaßen aussieht, so eine Dreiecksmatrix,

wo der untere Teil, das untere Dreieck mit lauter Nullen besetzt ist.

Dann können wir schön mit der Rücksubstitution nach und nach unsere einzelnen Unbekannten ausrechnen.

Gut, dann haben wir uns überlegt, wie wir das Ganze... also so schaut der Pseudocode aus.

Dann haben wir uns überlegt, wie das Ganze paralysiert werden kann.

Anhand des Diagramms haben wir festgestellt, dass eine Paralysierung entlang den Spalten eigentlich nicht möglich ist, sondern nur entlang den Zahlen.

Das heißt also die äußere Schleife, wo wir entlang den Zahlen runterlaufen.

In der inneren Schleife arbeiten wir in den Zahlen, aber die äußere Schleife ist also nicht parallelisierbar.

Die hier, da müssen wir jeweils immer warten, weil wir die einzelnen Xs erst einmal ausrechnen müssen.

Okay, dann haben wir uns an Zeilen und orientierten Ansatz angeguckt und an Spalten orientierten.

Wir stellen dann fest, dass für diese Körpere hier anschauen, dass bei kleinen N und großen P,

also wenn wir viele Prozessoren haben, dann die Aufteilung uns eigentlich mehr Zeit kostet als die Parallelisierung.

Morgen, und da ist noch was frei. Und da gibt es wahrscheinlich noch in der Bar drüben einen Stuhl.

Morgen. So, voila. Bitte schön. Also bis jetzt nicht. Ich weiß nicht, vielleicht, wenn nur einer kommt, dann haben wir da zwei.

Okay. So, setzen Sie sich ruhig, wieso einer hinter? Gut, und dann haben wir festgestellt, dass also da die Aufteilung zu weit

in den Nachrichtenübertragungszeit dominiert, wenn wir zu viele P's haben, also zu viele Prozessoren und zu kleine Ns,

dann bringt uns die Parallelisierung nichts, dann lassen wir das besser bleiben und setzen den zahlenorientierten Ansatz an,

weil da müssen wir nicht so viel übertragen. Im anderen Fall, dort wo N sehr groß ist,

können wir auch bei, wenn wir hier weiter drüben sind, mit großen Prozessoren den zahlenorientierten Ansatz wählen,

denn hier können wir dann entsprechend paralysieren. Gut, ja. Dann sind wir zur Gaus-Elimination gegangen,

weil die Rücksubstitution setzt ja voraus, dass wir eine Dreiecksmatrix haben, wo der untere Bereich lauter Nullen hat.

Das ist in der Regel erstmal nicht gegeben. Also brauchen wir die Gaus-Elimination, um jeweils Zahlen voneinander so abzuziehen,

dass wir hier lauter Nullen unterhalb dieser, wieder in dem unteren Dreiecksmatrix lauter Nullen bekommen. Also die Spalten hier müssen

jeweils um eins, um eine Zeile zunehmend immer lauter Nullen bekommen und dann haben wir die Dreiecksmatrix wieder gegeben

und dann können wir wieder den Rücksubstitutionsalgorithmus anwenden. Okay, so schaut also der Pseudocode aus.

Und ja, hier haben wir uns mal anhand dieses Diagramms dann überlegt, wie die Abschätzung ist.

Also erstmal laufen wir entlang der äußeren Schleife. Dann müssen wir jeweils immer dieses a hier übertragen

und dann muss das hier in den einzelnen Zeilen, muss der Faktor ausgerechnet werden und dann wird dieser Faktor,

das ist dann dieses t hier und dieses t muss dann mit allen, das ist die mittlere Schleife, das ist die mittlere Schleife hier,

muss dann mit allen hier multipliziert werden, mit allen Einträgen entlang der Zeile und wenn wir das dann haben,

dann können wir die innerste Schleife abarbeiten und die einzelnen Zeilen hier die neuen Werte bestimmen und dann voneinander abziehen.

Okay, ja dann haben wir uns noch angeguckt, was war dann das Problem?

Das Problem könnte es sein, dass wir häufig durch Zahlen dividieren, die recht nahe bei Null sind.

Und dadurch kriegen wir Ungenauigkeiten rein, das wollen wir vermeiden. Wie können wir das vermeiden?

Durch die sogenannte Pivotisierung. Das heißt, wir suchen uns die Spalte bzw. die Zeile heraus, die in der Spalte gerade das Maximum hat.

Wir rechnen nicht unbedingt jetzt mit dem Element, sondern wir schauen erst mal nach,

wo ist die Zeile, die in einer bestimmten Spalte das Maximum hat? Und dieses Maximum stellen wir dann nach oben.

Auf die Art und Weise erreichen wir, dass man dann nicht durch eine Zahl, die nahe bei Null ist, dividieren.

Und das könnte ja eine sehr große Zahl geben und dadurch kriegen wir die Ungenauigkeiten rein.

Okay, so war das. Ja, dann haben wir uns, genau, das sind die numerischen Stabilitätsfragen. Wo ist der Nachteil?

Der Nachteil ist, dass ich dann diese Zeilen austauschen muss.

Wenn ich hier das Maximum finde, müsste ich diese Zeile mit der da hier austauschen, um die nach oben zu bringen.

Weil diese Zeile, wenn die das Maximum hier enthält, muss die ja mit allen anderen dann reduziert werden.

Das ist lästig, weil da müsste ich viele Daten übertragen. Also was tun?

Man arbeitet mit einer Verzeigerung, das heißt also mit einer Liste, in der eigentlich nur Zeiger gespeichert sind.