[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

9.1 Speicherung schwach besetzter Matrizen

Index:

Einleitung:

Den Speicherformaten für schwach besetzte Systeme kommen aus zweierlei Gründen eine besondere Bedeutung zu:

  1. Die Wahl der Speicherform hat direkte Auswirkungen auf die verwendeten Lösungsverfahren (spezielle Matrixform, z.B. Bandmatrix, symmetrische Matrix, ...; Auffüllverhalten (Erzeugung neuer Nichtnullelemente) der verschiedenen Algorithmen und die Konsequenzen auf die Speicherstruktur).
  2. Als "normaler User" verwendet man im allgemeinen eines der vielen SLS-Pacs (Programmpakete mit fertig implementierten num. Algorithmen) zur Problemlösung. Diesen Pacs müssen die Daten aber in bestimmten Datenstrukturen übergeben werden.
Einige der heute gängigen Speicherformate werden hier nun vorgestellt.

Allgemeines:

In diesem Abschnitt gelten folgende Annahmen/Definitionen:


Bandmatrizen allgemein

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:

BILD NICHT DARSTELLBAR: grafisches Beispiel


Speicherung für iterative Verfahren

COO-Format: Koordinatenformat

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.

Beispiel:

... wird zu ... BILD NICHT DARSTELLBAR: grafisches Beispiel


Modifiziertes COO-Format

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

(i-1)n + j,
wenn i die Zeile und j die Spalte des Elementes in der Matrix bezeichnen (diese Darstellung ist eindeutig).

Die Reduktion des Speicherbedarfs gegenüber dem COO-Format wird aber durch folgende Nachteile erkauft:

  1. es sind zusätzliche Rechenschritte notwendig, um den ursprünglichen Zeilen- und Spaltenindex wieder herzustellen;
  2. der Wertebereich des INTEGER-Arrays "index" kann schnell gesprengt werden und die Verwendung von mehr als 16 Bit pro Indexeintrag nötig machen, was den Sinn dieses Formates ad absurdum führen würde.

In der Praxis ist dieses Speicherformat daher nur selten anzutreffen.


CRS-Format (auch CSR-Format): Komprimierte Zeilenspeicherung

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 ... BILD NICHT DARSTELLBAR: grafisches Beispiel


Modifiziertes CRS-Format

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.

Beispiel:

... wird zu ... BILD NICHT DARSTELLBAR: grafisches Beispiel


CCS-Format (auch Harwell-Boeing-Format): Komprimierte Spaltenspeicherung

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:


CDS-Format: Komprimiertes Diagonalformat

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 ... BILD NICHT DARSTELLBAR: grafisches Beispiel


BND-Format (auch LAPACK-Format): Bandmatrizenspeicherung

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.
Die Dimensionen des REAL-Arrays "value" sind natürlich weiterhin n x p+q+1.

Vor- und Nachteile dieses Formats sind gleich dem CDS-Format.

... wird zu ... BILD NICHT DARSTELLBAR: grafisches Beispiel


JDS-Format: Verschobenes Diagonalformat

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:

BILD NICHT DARSTELLBAR: grafisches Beispiel


SKS-Format: Skyline-Speicherung

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:

Spalteninformation muß nicht abgespeichert werden, sondern kann wie folgt berechnet werden:
In welcher Spalte beginnt die Zeile x?
x - [row-pointer(x+1) - row-pointer(x)] + 1

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 ... BILD NICHT DARSTELLBAR: grafisches Beispiel

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.


Speicherung für direkte Verfahren

Bandformat

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.

Beispiel:

... wird zu ... BILD NICHT DARSTELLBAR: grafisches Beispiel


Allgemeine Speicherformate

Verkettete Listen

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 ... BILD NICHT DARSTELLBAR: grafisches Beispiel

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.


Zyklisch verkettete Listen

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.

Beispiel:

... wird zu ... BILD NICHT DARSTELLBAR: grafisches Beispiel


[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]