Der Grad eines Knotens gibt die Anzahl der Verknüpfungen an. Für die Entstehung neuer
Elemente während der Faktorisierung gilt dabei folgende Regel (Fill-In-Regel):
Wird ein Knoten reduziert. so entstehen neue Graphen zwischen allen Knoten,
die mit dem reduzierten Knoten durch einen Graphen verbunden sind.
s SI? zz e
Abb.7: Reduktionsstufen eines Graphen
Aus dieser Regel kann unmittelbar der SchluB gezogen werden, daB bei der Faktorisie-
rung ein Fill-In in einer Spalte nur unterhalb eines von Null verschiedenen Elementes er-
folgen kann. Daher bietet sich zur Speicherung von Matrizen, die eine Besetzung haupt-
sáchlich in der Nàhe der Diagonalen aufweisen das Speicherschema von Jennings an, wenn
eine Faktorisierung erfolgen soll.
3.1 Speicherschema nach Jennnings
Bei dieser Speichermethode, die auch Profilspeichertechnik oder lineare Spaltenspeiche-
rung genannt wird, werden von jeder Spalte alle Elemente vom ersten Nicht-Null-Ele-
ment bis zur Diagonalen hintereinander in einem Vektor gespeichert, unabhängig davon,
ob diese Elemente einen Wert gleich oder ungleich Null haben /A.Jennings 1956,
J.Le Menestrel 1969. G.Schmitt 1973, H.R.Schwarz 1980/.
a; = |
X Sj -Sj-L7 pt itl (1)
| | pj = oi = gj efi AR
: : u
Profil der Matrix Psu+ EX (j - pj) (3)
u ~~] j^!
Hülle der Matrix
X
Abb.B: Profil und Hülle einer symmetrischen Matrix
Die Elemente der gespeicherten Spalten bilden das Profil P der Matrix (3) und werden
von der Hülle der Matrix umschlossen (Abb.8). Abbildung 9 zeigt die Speicherbelegung
für die Matrix in Abb.B. Zur Verwaltung der Matrix wird ein Profilvektor p aufgebaut.
der für jede Spalte die Zeilennummer des ersten gespeicherten Elements angibt [2).
Der Zugriff auf die Matrixelemente ist mit einem Adressvektor a móglich, der die Adres-
sen der Diagonalelemente der Matrix enthált. Profil- und Adressvektor kónnen ineinan-
der überführt werden: daher ist nur ein Vektor zu speichern (1).(2).
Im Gegensatz zu den reinen Sparse-Speichertechniken wird hier eine Anzahl von Null-.
elementen mit gespeichert. Damit wird jedoch der Nachteil der anderen Sparse-Techniken
vermieden, bei denen bei der Faktorisierung neu entstehende Elemente nur mit erheb-
