Compressed Row Storage

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Compressed Row Storage (CRS) oder Compressed Sparse Row (CSR) ist ein häufig genutztes Verfahren zum Speichern dünnbesetzter Matrizen. In der numerischen Mathematik bezeichnet man damit eine Matrix, bei der so viele Einträge aus Nullen bestehen, dass es sich lohnt, dies auszunutzen.

Beim CRS-Verfahren werden nur die von Null verschiedenen Einträge einer -Matrix gespeichert: In Form eines Arrays , also an aufeinanderfolgenden Stellen im Speicher. Die für die Abbildung zwischen Positionen in der Matrix und dem Array benötigten Informationen werden in zwei weiteren Arrays und gespeichert. In ist zu jedem Eintrag aus der Index seiner Spalte gespeichert. Er umfasst daher gleich viele Elemente wie . Die Werte in legen fest, welche Werte von zu welcher Zeile gehören.

Der formale Zusammenhang zwischen der Matrix und ihrer Darstellung unter Verwendung von CRS lautet:

Beispiel:
(Die blauen Zahlen geben die Zeilen und die grünen die Spalten der Matrix an. Die Indizes beginnen wie in vielen Computersprachen üblich mit 0.)

In diesem Beispiel sind in den drei Vektoren folgende Werte gespeichert:

Sowohl als auch enthalten 7 Elemente, dies entspricht immer der Anzahl der Nichtnullelemente in . hat 5 Elemente; die Anzahl der Elemente ist immer um 1 größer als die Anzahl der Zeilen von . Das Element 0 hat den Wert 0, das letzte Element gibt die Größe von an, in diesem Fall 7.

Die Rekonstruktion der Zeile 1 der Matrix aus der komprimierten Speicherform geschieht folgendermaßen: Die Elemente 1 und 2 des Vektors zeigen an, dass an der Stelle 2 der Vektoren und die Zeile 1 und an der Stelle 4 die folgende Zeile beginnt. Die Zeile 1 hat also zwei von 0 verschiedene Elemente. Ihre Spaltenindizes stehen an den Stellen 2 und 3 von , ihre Werte an den entsprechenden Stellen in : 11 in der Spalte 2 und 13 in der Spalte 4.