Eine Matrix wird normalerweise als zweidimensionales Array gespeichert. Jeder Eintrag im Array steht für ein Element ai,j der Matrix und wird über die beiden Indizes i und j angesprochen. Üblicherweise ist i der Zeilenindex, der von oben nach unten nummeriert ist, und j der Spaltenindex, der von links nach rechts nummeriert ist. Für eine m × n-Matrix ist der für die Speicherung der Matrix in diesem Format erforderliche Speicherplatz proportional zu m × n (ohne Berücksichtigung der Tatsache, dass auch die Dimensionen der Matrix gespeichert werden müssen).
Im Falle einer dünn besetzten Matrix kann der Speicherbedarf erheblich reduziert werden, indem nur die Nicht-Null-Einträge gespeichert werden. Je nach Anzahl und Verteilung der Nicht-Null-Einträge können verschiedene Datenstrukturen verwendet werden, die im Vergleich zum Basisansatz enorme Speichereinsparungen bringen. Der Nachteil ist, dass der Zugriff auf die einzelnen Elemente komplexer wird und zusätzliche Strukturen benötigt werden, um die ursprüngliche Matrix eindeutig wiederherstellen zu können.
Formate können in zwei Gruppen unterteilt werden:
- Diejenigen, die eine effiziente Modifikation unterstützen, wie DOK (Dictionary of keys), LIL (List of lists) oder COO (Coordinate list). Diese werden in der Regel zum Aufbau von Matrizen verwendet.
- Diejenigen, die einen effizienten Zugriff und Matrixoperationen unterstützen, wie CSR (Compressed Sparse Row) oder CSC (Compressed Sparse Column).
Dictionary of keys (DOK)Edit
DOK besteht aus einem Wörterbuch, das (Zeilen-, Spalten)-Paare auf den Wert der Elemente abbildet. Elemente, die im Wörterbuch fehlen, werden als Null angenommen. Das Format eignet sich gut für den schrittweisen Aufbau einer dünn besetzten Matrix in zufälliger Reihenfolge, aber schlecht für die Iteration über Nicht-Null-Werte in lexikographischer Reihenfolge. In der Regel wird eine Matrix in diesem Format erstellt und dann für die Verarbeitung in ein anderes, effizienteres Format konvertiert.
List of lists (LIL)Edit
LIL speichert eine Liste pro Zeile, wobei jeder Eintrag den Spaltenindex und den Wert enthält. Normalerweise werden diese Einträge nach dem Spaltenindex sortiert gespeichert, um schneller nachschlagen zu können. Dies ist ein weiteres Format, das sich für den inkrementellen Matrixaufbau eignet.
Koordinatenliste (COO)Bearbeiten
COO speichert eine Liste von (Zeile, Spalte, Wert) Tupeln. Idealerweise werden die Einträge zuerst nach Zeilenindex und dann nach Spaltenindex sortiert, um die Zugriffszeiten zu verbessern. Dies ist ein weiteres Format, das sich gut für den inkrementellen Matrixaufbau eignet.
Compressed sparse row (CSR-, CRS- oder Yale-Format)Bearbeiten
Das CSR- (Compressed sparse row) oder CRS- (Compressed Row Storage) oder Yale-Format stellt eine Matrix M durch drei (eindimensionale) Arrays dar, die jeweils Nicht-Null-Werte, die Ausmaße von Zeilen und Spaltenindizes enthalten. Es ist ähnlich wie COO, komprimiert aber die Zeilenindizes, daher der Name. Dieses Format ermöglicht einen schnellen Zeilenzugriff und Matrix-Vektor-Multiplikationen (Mx). Das CSR-Format wird seit mindestens Mitte der 1960er Jahre verwendet, wobei die erste vollständige Beschreibung 1967 erschien.
Das CSR-Format speichert eine dünnbesetzte m × n-Matrix M in Zeilenform unter Verwendung von drei (eindimensionalen) Arrays (V, COL_INDEX, ROW_INDEX). NNZ bezeichne die Anzahl der Nicht-Null-Einträge in M. (Beachten Sie, dass hier Indizes auf Nullbasis verwendet werden.)
- Die Arrays V und COL_INDEX haben die Länge NNZ und enthalten die Nicht-Null-Werte bzw. die Spaltenindizes dieser Werte.
- Das Array ROW_INDEX hat die Länge m + 1 und kodiert den Index in V und COL_INDEX, mit dem die gegebene Zeile beginnt. Das letzte Element ist NNZ , d.h., der fiktive Index in V unmittelbar nach dem letzten gültigen Index NNZ – 1.
Zum Beispiel die Matrix
( 5 0 0 0 0 8 0 0 0 0 3 0 0 6 0 0 ) {\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&3&0\\0&6&0&0\\\end{pmatrix}}
ist eine 4 × 4-Matrix mit 4 Nicht-Null-Elementen, also
V = COL_INDEX = ROW_INDEX =
unter der Annahme einer null-indizierten Sprache.
Um eine Zeile zu extrahieren, definieren wir zunächst:
row_start = ROW_INDEX row_end = ROW_INDEX
Dann nehmen wir Slices von V und COL_INDEX, beginnend bei row_start und endend bei row_end.
Um die Zeile 1 (die zweite Zeile) dieser Matrix zu extrahieren, setzen wir row_start=1 und row_end=2. Dann machen wir die Slices V = und COL_INDEX = . Wir wissen nun, dass in Zeile 1 ein Element in Spalte 1 mit dem Wert 8 vorhanden ist.
In diesem Fall enthält die CSR-Darstellung 13 Einträge, im Vergleich zu 16 in der ursprünglichen Matrix. Das CSR-Format spart nur dann Speicher, wenn NNZ < (m (n – 1) – 1) / 2.Ein weiteres Beispiel, die Matrix
( 10 20 0 0 0 0 0 30 0 40 0 0 0 0 50 60 70 0 0 0 0 0 80 ) {\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}
ist eine 4 × 6 Matrix (24 Einträge) mit 8 Elementen ungleich Null, so
V = COL_INDEX = ROW_INDEX =
das Ganze wird als 21 Einträge gespeichert.
- ROW_INDEX teilt das Array V in Zeilen auf:
(10, 20) (30, 40) (50, 60, 70) (80); - COL_INDEX ordnet die Werte in Spalten an:
(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).
Beachten Sie, dass in diesem Format der erste Wert von ROW_INDEX immer Null und der letzte immer NNZ ist, so dass sie in gewissem Sinne redundant sind (obwohl in Programmiersprachen, in denen die Array-Länge explizit gespeichert werden muss, NNZ nicht redundant wäre). Nichtsdestotrotz vermeidet dies die Notwendigkeit, einen Ausnahmefall bei der Berechnung der Länge jeder Zeile zu behandeln, da es garantiert, dass die Formel ROW_INDEX – ROW_INDEX für jede Zeile i funktioniert. Außerdem sind die Speicherkosten dieser redundanten Speicherung für eine ausreichend große Matrix wahrscheinlich unbedeutend.
Die (alten und neuen) Yale Sparse-Matrix-Formate sind Instanzen des CSR-Schemas. Das alte Yale-Format arbeitet genau wie oben beschrieben mit drei Arrays; das neue Format kombiniert ROW_INDEX und COL_INDEX in einem einzigen Array und behandelt die Diagonale der Matrix separat.
Für logische Adjazenzmatrizen kann das Datenarray weggelassen werden, da die Existenz eines Eintrags im Zeilenarray ausreicht, um eine binäre Adjazenzbeziehung zu modellieren.
Es ist wahrscheinlich als das Yale-Format bekannt, weil es 1977 im Bericht über das Yale Sparse Matrix Package vom Department of Computer Science der Yale University vorgeschlagen wurde.
Compressed Sparse Column (CSC oder CCS)Bearbeiten
CSC ist ähnlich wie CSR, außer dass Werte zuerst spaltenweise gelesen werden, ein Zeilenindex für jeden Wert gespeichert wird und Spaltenzeiger gespeichert werden. CSC ist zum Beispiel (val, row_ind, col_ptr), wobei val ein Array der (von oben nach unten, dann von links nach rechts) Nicht-Null-Werte der Matrix ist; row_ind sind die den Werten entsprechenden Zeilenindizes; und col_ptr ist die Liste der val-Indizes, mit denen jede Spalte beginnt. Der Name beruht auf der Tatsache, dass die Spaltenindexinformationen gegenüber dem COO-Format komprimiert sind. Üblicherweise verwendet man ein anderes Format (LIL, DOK, COO) für die Konstruktion. Dieses Format ist effizient für arithmetische Operationen, Spaltenzerlegung und Matrix-Vektor-Produkte. Siehe scipy.sparse.csc_matrix, das traditionelle Format zur Angabe einer Sparse-Matrix in MATLAB (über die Funktion sparse).