Beispiel:
Kreise stehen für Nullen, gefüllte Quadrate für Matrixelemente ungleich Null.
Den Speicherformaten für schwach besetzte Systeme kommen aus zweierlei Gründen eine besondere Bedeutung zu:
In diesem Abschnitt gelten folgende Annahmen/Definitionen:
Bandmatrizen, bei denen innerhalb der Bandbreite nur wenige Elemente gleich Null sind, können relativ einfach kompakt gespeichert werden. Man verwendet dafür ein 2-dimensionales Feld mit den Abmessungen n x Bandbreite. In dieses Feld werden die Diagonalen der ursprünglichen Matrix als Zeilen im neuen Feld gespeichert, die Spalten werden beibehalten.
Beispiel:
Das COO-Format ist das einfachste Speicherformat für schwach besetzte Matrizen.
Es verwendet 3 eindimensionale Arrays der Länge non-null(A):
Dieses Format wird häufig wegen seiner Einfachheit verwendet (dient
oft als eine von vielen möglichen Schnittstelle zu SLS-Pacs).
Der Umstand, daß die Nichtnull-Matrixelemente in beliebiger Reihenfolge
im Feld "value" stehen dürfen, ist sowohl ein Vorteil als auch
ein Nachteil des COO-Formats. Einerseits können die bei
der Lösung des Gleichungssystems neu auftretenden Nichtnullelemente
einfach am Ende der Felder ohne irgendwelchen Umordnungsaufwand angehängt
werden. Andererseits ist der Suchaufwand nach einem bestimmten
Matrixelement enorm, da ja keinerlei Strukturinformation der Matrix
A in das Speicherformat selbst eingeht (ist das gesuchte Element
gleich Null, müssen die Felder komplett durchsucht werden, bis diese
Information vorliegt).
Ein weiterer Nachteil ist auch der immer noch recht hohe Speicherbedarf.
... wird zu ...
Hier wird versucht, den Speicheraufwand des COO-Formats zu reduzieren.
Statt den beiden INTEGER-Arrays "row-index" und
"col-index" wird nur noch ein INTEGER-Feld "index"
benötigt, um die Koordinaten des Nichtnullelementes in "value"
zu speichern. Der Wert errechnet sich nach der Formel
Die Reduktion des Speicherbedarfs gegenüber dem COO-Format wird aber durch folgende Nachteile erkauft:
In der Praxis ist dieses Speicherformat daher nur selten anzutreffen.
Das CRS-Format ist bereits eine relativ kompakte Speicherform, die aber nicht von einer bestimmten Struktur der Matrix A ausgeht. Sinn dieses Formates ist es, sehr schnell alle Nichtnullelemente einer bestimmten Zeile zu finden.
Es verwendet 3 eindimensionale Arrays, 2 der Länge non-null(A) und 1 mit der Länge n+1:
Das CRS-Format benötigt gegenüber dem
COO-Format
doch deutlich weniger Speicher (vgl. dazu den
Speicherplatzbedarf der in der Einleitung zu diesem Kapitel vorgestellten
Matrix "BCSSTK32" aus der Harwell-Boeing Sparse Matrix
Collection). Auch das Suchen nach einem bestimmten Matrixelement
geht hier deutlich schneller.
Werden vom Lösungsalgorithmus aber neue Nichtnullelemente erzeugt, dann
ist die Einordnung doch komplizierter und auch mit mehr Aufwand verbunden als
beim COO-Format.
Das CRS-Format ist das Basisformat für das SLS-Pac "SPARSKIT".
Beispiel:
... wird zu ...
Beim MRS-Format wird nochmals versucht, den ohnehin schon geringen Speicherplatzbedarf des CRS-Formats noch weiter zu senken.
Hier geht man davon aus, daß die Hauptdiagonale voll (oder zumindest überdurchschnittlich hoch) besetzt ist, eine Bedingung, die fast alle in der Praxis vorkommenden Matrizen erfüllen. Speichert man nun die Hauptdiagonale extra ab, so wird keinerlei zusätzliche Koordinateninformation dafür benötigt, denn man weiß ja, daß z.B. das dritte Hauptdiagonalelement in der dritten Zeile und der dritten Spalte steht.
Diese Grundidee wird im MRS-Format folgendermaßen umgesetzt:
Vor- und Nachteile dieser Speicherform sind ähnlich dem
CRS-Format.
Das MRS-Format ist relativ beliebt.
... wird zu ...
Dieses Format entspricht im wesentlichen dem CRS-Format , nur daß man hier nicht schnell auf eine Zeile, sondern eine komplette Spalte zugreifen möchte.
Hier eine kurze Beschreibung der Veränderungen zum CRS-Format:
Dieses Format geht von einer Bandstruktur der Matrix A aus.
Außerdem sollte für das CDS-Format die Bandbreite
relativ klein und konstant, der Besetztheitsgrad innerhalb des Bandes hoch
sein.
Durch die Speicherung der Neben- und Hauptdiagonalen der Matrix A
nach einem bestimmten Muster (nebeneinander) werden Zusatzinformationen zu
den Koordinaten der einzelnen Elemente bzw. der Zeilen (Spalten)
überflüssig, es werden nur zwei zusätzliche
INTEGER-Zahlen p und q, die obere und untere
Bandbreite der Matrix A
(siehe Abschnitt Allgemeines ) zur
eindeutigen Dekodierung benötigt.
Im wesentlichen besteht das CDS-Format aus einem rechteckigen REAL-Array "value" mit den Abmessungen n x p+q+1, in das von oben nach unten die Matrixdiagonalen von unten nach oben eingetragen werden. Die Indizes der zweiten Dimension kann man sich von -p bis q gehend vorstellen. Dieser Index gibt an (absolut genommen), wieviel die entsprechende Diagonale eingerückt werden muß (Diagonalen unterhalb der Hauptdiagonalen von links, oberhalb von rechts). Die so freigelassenen Felder im Array "value" werden mit Nullen aufgefüllt.
Der Vorteil dieses Formats besteht darin, daß keine Koordinaten zu den
einzelnen Elementen der Matrix A abgespeichert werden müssen,
da die gesamte Strukturinformation der Matrix im Speicherformat erhalten
bleibt.
Allerdings, wie man auch am folgenden Beispiel erkennt, ist der
Speicherplatzgewinn sehr stark von der Bandbreite und der Anzahl der Nullen
innerhalb des Bandes abhängig. Man sollte sich also die Matrix sehr gut
anschauen, bevor man versucht, sie mit Hilfe des CDS-Formats
abzuspeichern.
Erwähnenswert ist vielleicht noch, daß das SLS-Pac "LINPACK" die Dimensionen des Arrays "value" umdreht, also p+q+1 x n verwendet.
Beispiel:
... wird zu ...
Das BND-Format ist dem CDS-Format sehr ähnlich. Es geht ebenfalls von einer Bandstruktur der Matrix A aus. Hier wird allerdings darauf Wert gelegt, daß die Spalten der Matrix auch im Array "value" erhalten bleiben.
Außer einer Verschiebung der Diagonalen, sodaß die Elemente einer Spalte untereinander liegen, ändert sich gegenüber dem CDS-Format nur noch, daß die Diagonalen oberhalb der Hauptiagonalen zuerst eingetragen werden, die Matrix A also von oben nach unten durchlaufen wird.
Vor- und Nachteile dieses Formats sind gleich dem CDS-Format.
... wird zu ...
Auch dieses Format ist für Bandmatrizen entwickelt worden. Es versucht,
an den Vorraussetzung für die Anwendung der Formate
CDS und
BND
zu "kratzen". Es ist besonders gut geeignet für
Matrizen mit größerer Bandbreite und einem nicht allzu hohen
Besetzheitsgrad innerhalb dieser Bandbreite.
Allerdings geht bei dieser kompakteren Speicherform wieder Strukturinformation
verloren. Diese muß daher in einem eigenen Feld zusätzlich
abgespeichert werden.
Nun zur Vorgangsweise:
Zunächst wird die ursprüngliche Matrix dahingehend verändert,
daß die Nichnullelemente links zusammengeschoben werden. Es entsteht
eine neue Matrix, die schmäler ist als die Ausgangsmatrix (wenn diese
wirklich eine Bandmatrix ist). Die Breite wird bestimmt durch die maximale
Anzahl von Nichtnullelementen in einer Zeile (m). Schmälere
Zeilen müssen mit Nullen rechts aufgefüllt werden.
Diese Zeilen werden nun in einem rechteckigen REAL-Array "value"
mit den Abmessungen n x m als Spalten abgespeichert.
Zusätzlich wird aber für jedes Element noch die Spalteninformation
aus der Ausgangsmatrix benötigt. Diese wird in einem eigenen
INTEGER-Array "col-index" mit den gleichen Dimensionen wie
"value" abgelegt.
Einen wirklichen Speicherplatzvorteil erhält man bei diesem Format nur,
wenn die maximale Anzahl an Nichtnullelementen in einer Zeile in der gesamten
Matrix nicht allzusehr schwankt. Dann nämlich wird die Anzahl der
gespeicherten Nullen reduziert.
Um auch größere Schwankungen der Anzahl der Elemente ungleich Null
in den verschiedenen Zeilen zu unterstützen, gibt es eine
Verallgemeinerung dieses JDS-Formats, welches aber im
großen und ganzen auf eine verkomplizierte Version des
CRS-Formats
hinausläuft. Daher wird es hier nicht beschrieben.
Das JDS-Format ist besonders im Bereich der Parallel- und Vektorrechner beliebt. Außerdem ist es das Standardformat für das SLS-Pac "ITPACK".
Beispiel:
Das SKS-Format ist ebenfalls für Bandmatrizen entwickelt
worden, allerdings für symmetrische. Außerdem wird versucht,
schwankenden Bandbreiten Herr zu werden.
Bei symmetrischen Matrizen ist es nur notwendig, die untere Dreiecksmatrix
abzuspeichern. Benötigt man ein Element aus der oberen Dreiecksmatrix,
so müssen zunächst die Indizes umgerechnet werden.
Es werden 2 eindimensionale Arrays verwendet:
Vorteil des SKS-Formats ist sicher der geringe
Speicherplatzbedarf.
Der Umstand, daß doch eine etwas längere Rechnung für die
Spaltenindexgewinnung benötigt wird, ist aber auch nicht unbedingt als
Nachteil zu sehen, bedenkt man, daß diese Berechnung für jede
Zeile nur 1x durchgeführt werden muß.
Beispiel:
... wird zu ...
An der Beispielmatrix A ist noch etwas besonderes, auf daß man in der Praxis aufpassen sollte. Diese Matrix zerfällt in zwei unabhängige Teilsysteme (angedeutet durch die punktierten Linien). Natürlich sind die Teilsysteme jedes für sich in Summe viel effizienter (Speicherplatz und Rechengeschwindigkeit) lösbar als die gesamte Matrix.
Dieses Format ist besonders auf die Bedürfnisse der
Gauß-Elemination mit Spaltenpivotsuche bei Bandmatrizen
zugeschnitten.
Bei diesem Algorithmus und dieser Matrixform weiß man schon im voraus,
an welchen Stellen der Matrix Auffüllung (neue Nichtnullelemente)
stattfindet. Diese Stellen können daher schon von Beginn an
mitberücksichtigt werden; es entfällt der bei manch anderen Formaten
doch erhebliche Umordnungsaufwand bei neu einzutragenden Elementen.
Zur Speicherung wird nur ein zweidimensionales REAL-Array "value"
mit den zusätzlichen INTEGER-Werten p und q
(siehe Abschnitt Allgemeines )
benötigt.
Das Feld "value" mit den Dimensionen n x
2p+q+1 (das ist die maximale Bandbreite, in der Auffüllung
stattfinden kann) wird von unten nach oben mit den Diagonalen der Matrix
A, ebenfalls von unten nach oben, aufgefüllt. Die oberen
p Zeilen werden mit Nullen gefüllt. Links oben und rechts
unten entstehen in dem rechteckigen Bereich Dreiecke, die nicht verwendet
werden.
Die Spalten der Ursprungsmatrix bleiben im Bandformat
erhalten, die Zeilen der Ausgangsmatrix sind Diagonalen von links unten nach
rechts oben im Array "value" (diese Informationen sind wichtig
für den Algorithmus, der z.B. Zeilenvertauschungen durchführen
muß).
Speicherplatz wird natürlich nur dann gespart, wenn 2p+q+1
deutlich kleiner ist als n.
... wird zu ...
Viele Algorithmen benötigen raschen Zugriff auf Elemente einer Zeile oder
Spalte (z.B. für Matrix-Vektor-Produkte). Formate, die dies
unterstützen, haben in der Regel Probleme mit neu einzuordnenden
Elementen (z.B.
CRS-Format ).
Eine Lösung für die eben genannten Probleme kann zum Beispiel eine
Mischung aus CRS- und
COO-Format
mit einer zusätzlichen Zeilen- (Spalten-)verkettung sein.
Man baut zunächst das normale CRS-Format mit seinen Feldern "value", "col-index" und "row-pointer" auf. Zusätzlich wird noch ein INTEGER-Array "row-list" der Länge non-null(A) benötigt, in dem für jedes Element in "value" der Index des nächsten Elementes in der gleichen Zeile steht. Ist es das letzte Element, dann wird eine Null eingetragen. Neue Nichtnullelemente können nun einfach wie beim COO-Format am Ende der Arrays angehängt werden. Für die entsprechende Zeile müssen nur zwei "row-list"-Einträge aktualisiert werden.
Diese Art von Formaten ist sehr flexibel, hat aber auch so seine Tücken (siehe Kommentar zum Beispiel).
Beispiel:Beispiel einer verketteten Liste die entsteht, wenn das ELement 46 erst nachträglich hinzugefügt wird.
... wird zu ...
Dieses Beispiel kann man als ein CRS-Format mit Zeilen und
Spaltenverkettung bezeichnen. Allerdings ist das Feld "col-list"
hier relativ überflüssig ohne ein eigenes Array
"col-pointer" und weiterer Zusatzinformation. Z.B. kann nie auf
eine ganze Spalte schnell zugegriffen werden, da man nur die Elemente
unterhalb eines Matrixelements gleich erreichen kann. Man benötigt daher
für eine komplette Spalte der Ausgangsmatrix das oberste Element in
der betreffenden Kolonne - in welcher Reihe befindet sich dieses?
Außerdem, wenn man ein Element in der gleichen Spalte mittels des Feldes
"col-list" gefunden hat, in welcher Zeile befindet sich
dieses?
Dieses Beispiel mahnt zur Vorsicht. Immer genau überlegen, welche
Informationen benötigt der gewählte Lösungsalgorithmus schnell
und häufig. Diese sollten gespeichert werden, netten "Firlefanz" kann
man getrost streichen.
Eine weitere Möglichkeit, Algorithmen raschen Zugriff auf Elemente einer Zeile oder Spalte zu gestatten, andererseits auch das Problem mit neuen Nichtnullelementen zufriedenstellend zu lösen, besteht in der Anwendung zyklisch verketteter Listen.
Man kann z.B. eine stark an das MRS-Format errinernde Speicherform mit 3 eindimensionalen Arrays der Länge n + non-null(A) verwenden:
Vorteil dieser Speicherform ist die große Flexibilität und der
doch recht geringe Speicherplatzaufwand.
Doch auch dieses Format hat einen kleinen Pferdefuß: Wie im folgenden
Beispiel gezeigt, ist es wirklich sehr leicht, alle Elemente einer Spalte
(hier Nummer 4) zu bekommen. Doch in welcher Zeile befindet sich
jedes dieser Elemente? Für das Matrixelement 34 werden die
Schritte, die zur Feststellung des Zeilenindex benötigt werden,
aufgezeigt. Es müssen die Verweise im Array "row" solange
verfolgt werden, bis man auf einen abgespeicherten Index stößt,
der kleiner oder gleich n ist. Erst dann weiß man, daß,
in diesem Beispiel, das Matrixelement 34 in Zeile 3
liegt.
Auch hier sollte man sich wieder sehr gut überlegen, ob der Aufwand
zur Feststellung des richtigen Zeilen/Spaltenindex die Speicherplatzersparnis
rechtfertigt. Ist die Anzahl der Nichtnullelemente in einer Zeile/Spalte
sehr klein, kann man vielleicht mit dieser Datenstruktur leben. Aber ab
einem gewissen (anwendungsspezifischen) Punkt sollte man doch die
Möglichkeit einer seperaten Speicherung der Zeilen- und/oder
Spaltenindizes in Betracht ziehen.
... wird zu ...
