4.1 Zeilenorientiertes Matrixkompressionsverfahren



next up previous contents
Next: 4.2 Hüllenorientierte Techniken Up: 4 Lösung des Gleichungssystems Previous: 4 Lösung des Gleichungssystems

4.1 Zeilenorientiertes Matrixkompressionsverfahren

 

Das Verfahren der konjugierten Gradienten (CG-Verfahren) zur Lösung des linearen Gleichungssystems konsumiert bei der Matrix-Vektor-Multiplikation, die innerhalb der Iterationsschleife liegt, einen Großteil seiner Rechenzeit. Es soll im weiteren Verlauf gezeigt werden, wie trotz der aufwendigeren Matrixstruktur diese Multiplikation effizient implementiert werden kann.

Zunächst soll die Struktur eines MCSR-(Modified Compressed Sparse Row)-Matrixformates an einem Beispiel erklärt werden.

Als Beispiel wird die symmetrische Matrix mit der Struktur

 

für die weiteren Betrachtungen auf eine untere Dreiecksmatrix und die Diagonaleinträge reduziert.

 

Die Diagonaleinträge nehmen in der Matrix eine Sonderstellung ein, da bei positiv definiten Systemen die Diagonale immer voll besetzt ist und die Matrix oft so skaliert wird, daß die Diagonaleinträge zu eins werden. Da bei Vorwärtseliminationen und Rücksubstitutionen nach Abarbeitung einer Zeile durch den Diagonaleintrag dividiert wird ((4.13),(4.15)), erweist es sich als günstig, die Diagonaleinträge in einem gesonderten Feld

abzuspeichern. Die restlichen Einträge der unteren Dreiecksmatrix, die ungleich Null sind, werden in einem eindimensionalen Feld

abgespeichert. Ein paralleles Indexfeld

gibt an, zu welcher Spalte der jeweilige Eintrag in der Matrix zuzuordnen ist. Ein zusätzliches Feld

legt den Beginn einer neuen Zeile mit einer Referenz in fest, wobei der letzte Eintrag von den Beginn der virtuellen Zeile der Matrix beschreibt, um das letzte Zeilenende festzusetzen. Die Gesamtlänge der Felder und ist also .

Der Zugriff auf einen gewissen Matrixeintrag ist mit einer Suche im Indexfeld verbunden. Möchte man zum Beispiel den Eintrag ermitteln, so liefert für die fünfte Zeile den Spaltenstart 3 und das Spaltenende 5. Nun sucht man das Indexfeld von der Stelle 3-5 nach dem Eintrag 3 ab und findet diesen an der Stelle 4. Damit ist der gewünschte Koeffizient im Feld an der Stelle 4 mit dem Wert 5.3 gefunden.

Die Einträge in und können innerhalb einer Matrixzeile unsortiert vorliegen. Sortiert man aber nach den Spaltenindizes , so kann man mit einer binären Suche den Aufwand reduzieren. Die Anzahl der Einträge der Zeile soll mit bezeichnet werden, und die Anzahl der Einträge in die untere Dreiecksmatrix . Da bei vielen Matrixstrukturen unter Verwendung quadratischer Ansatzfunktionen die gemittelte Anzahl der Einträge pro Zeile von bei etwa liegt, findet man mit maximal vier Teilungen das Auslangen.

Veranschlagt man für das Gleitkommafeld acht Bytes pro Eintrag und für das Indexfeld vier Bytes, so ergibt sich unter der Annahme einer vollbesetzten Matrix ein zusätzlicher Speicheraufwand von etwas mehr als gegenüber einer unkomprimierten Matrix. Da die gemittelte Anzahl der Einträge pro Zeile nicht mit der Größe des Ranges korreliert, wird die Effizienz des MCSR-Verfahrens um so besser, je größer der Rang des Gleichungssystems ist.

Die Matrix-Vektor-Multiplikation ist die einzige Operation, die bei der CG-Methode direkt auf die Matrix angewendet wird. Da für die Multiplikation

die Gesamtmatrix benötigt wird, jedoch nur die untere triangulare Matrix und Diagonale vorhanden ist, soll die Multiplikation in die Teilaufgaben

zerlegt werden.

Den Multiplikationsanteil der Diagonale und der unteren Dreiecksmatrix, ausgehend von dem MCSR-Matrix-Format, zeigt der folgende Pseudo-Code:

 

Den oberen Matrixanteil berechnet man ebenso einfach durch das Programm:

 

Bemerkenswert ist, daß keinerlei Suche von Matrixeinträgen notwendig ist und Multiplikationen mit Einträgen, die Null sind, vollständig unterdrückt werden.

Das bedeutet, daß trotz eines Zeilenkompressionsverfahrens der Anteil ohne Mehraufwandgif gegenüber dem Anteil berechnet werden kann.

Die Programmteile (4.3) und (4.4) lassen sich natürlich zu

 

zusammenfassen. Der Aufwand der Vektor-Matrix-Multiplikation liegt, durch das MCSR-Format bedingt, statt bei multiply-adds bei multiply-adds.

Für den in Abschnitt 4.5.4.1 gezeigten ICCG-Gleichungslöser ist pro Iteration eine Vorwärtselimination und Rücksubstitution, die ebenso auf dem MCSR-Format arbeitet, durchzuführen. Die Implementierung der Vorwärtselimination und Rücksubstitution hat große Ähnlichkeit mit den gezeigten Teilmultiplikationen (4.3) und (4.4), und ist daher genauso effizient machbar.



next up previous contents
Next: 4.2 Hüllenorientierte Techniken Up: 4 Lösung des Gleichungssystems Previous: 4 Lösung des Gleichungssystems



Martin Stiftinger
Fri Nov 25 16:50:24 MET 1994