4.2 Hüllenorientierte Techniken



next up previous contents
Next: 4.2.1 Einfluß der Knotennumerierung Up: 4 Lösung des Gleichungssystems Previous: 4.1 Zeilenorientiertes Matrixkompressionsverfahren

4.2 Hüllenorientierte Techniken

 

Wie schon zu Beginn des Kapitels 4 erläutert wurde, ist für direkte Gleichungslöser eine Matrixstruktur zur Verfügung zu stellen, die zwischen den von Null verschiedenen Einträgen auch für Nulleinträge Speicherplätze reserviert, da während einer Matrixfaktorisierung diese Einträge aufgefüllt werden.

Für die weiteren Erläuterungen soll zunächst der Begriff der Bandbreite einer Zeile erklärt werden, welche die Differenz vom maximalen zum minimalen von Null verschiedenen Spaltenindex einer Zeile

angibt.

Da mit symmetrischen Matrizen gearbeitet wird, ist es sinnvoll, auch für die untere Dreiecksmatrix eine linksseitige Bandbreite

zu definieren. Die Matrix (4.2) weist also Bandbreiten

auf.

Das Profil einer Matrix bzw. das Profil einer unteren Dreiecksmatrix ist mit

definiert. Das Profil entspricht der Anzahl der Elemente von , welche im Verlauf der Faktorisierung benutzt werden. Im symmetrischen Fall kann die Faktorisierung so aufgebaut werden, daß nur auf der strikten unteren Dreiecksmatrix und den Diagonaleinträgen gearbeitet wird.

Die hüllenorientierte Abspeicherung der Matrix soll wieder an dem Beispiel (4.2) erläutert werden. Da die Diagonalelemente wieder eine ausgezeichnete Stellung einnehmen, werden sie wieder in einem dafür vorgesehenen Feld

abgespeichert. In dem eindimensionalen Feld , das die Einträge der strikten unteren Dreiecksmatrix abspeichert, müssen nun auch die Nullen, die innerhalb der Hülle liegen, berücksichtigt werden.

Das Feld behält seine Funktion - es markiert den Anfang einer Zeile in .

Das Indexfeld wird nun auf Einträge gekürzt. Es enthält nun den ersten von Null verschiedenen Spaltenindex jeder Zeile

Man erkennt, daß man mit der gleichen Matrixstruktur die beiden Matrixformate abspeichern kann. Das Beispiel sollte nicht zur Annahme verleiten, daß dieses Verfahren speicherplatzsparender als das zeilenkomprimierte Matrixkompressionsverfahren ist, da das Indexfeld entfällt. Bei diesem einfachen Beispiel ist die Zahl der Hülleneinträge nahezu gleich den Einträgen des MCSR-Formates. Bei realistischen Beispielen ist jedoch die Zahl der Nulleinträge ein Vielfaches der restlichen Einträge.





next up previous contents
Next: 4.2.1 Einfluß der Knotennumerierung Up: 4 Lösung des Gleichungssystems Previous: 4.1 Zeilenorientiertes Matrixkompressionsverfahren



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