Compressed Row Storage

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 (mxn)-Matrix A gespeichert: In Form eines Arrays val, also an aufeinanderfolgenden Stellen im Speicher. Die für die Abbildung zwischen Positionen in der Matrix und dem Array val benötigten Informationen werden in zwei weiteren Arrays rowPtr und colInd gespeichert. In colInd ist zu jedem Eintrag aus val der Index seiner Spalte gespeichert. Er umfasst daher gleich viele Elemente wie val. Die Werte in rowPtr legen fest, welche Werte von val zu welcher Zeile gehören.

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

$A_{i,j} =val[k] \iff (colInd[k] = j ) \and ( rowPtr[i] \leq k < rowPtr[i+1] ).$

Beispiel:

$A= \begin{pmatrix} 10 & 0 & 0 & 12 & 0 \\ 0 & 0 & 11 & 0 & 13 \\ 0 & 16 & 0 & 0 & 0 \\ 0 & 0 & 11 & 0 & 13 \\ \end{pmatrix}$

In diesem Beispiel sind in diesen 3 Vektoren folgende Werte gespeichert:

$\begin{matrix} val &= & (10 & 12 & 11 & 13 & 16 & 11 & 13) \\ colInd &= & (1 & 4 & 3 & 5 & 2 & 3 & 5) \\ rowPtr &= & (0 & 2 & 4 & 5 & 7) & & \end{matrix}$

Es enthalten val sowie colInd je 7 Elemente (entspricht immer Anzahl der Nichtnullelemente in A) und rowPtr 5 Elemente (entspricht immer der Anzahl Reihen in A plus 1).

Die Rekonstruktion der vollständigen Matrix aus der komprimierten Speicherform geschieht folgendermaßen: Der Wert 0 des Vektors rowPtr zeigt an, dass an der 1. Stelle der Vektoren val und colind eine neue Zeile beginnt. (Die erste Position in Vektoren hat in Computersprachen i.d.R. den Index 0.) Diese hat die von 0 verschiedenen Elemente 10 in der 1. Spalte und 12 in der 4.Spalte. An der 3. Position (Vektor-Index 2, siehe rowPtr) beginnt die nächste Zeile mit den Elementen 11 in Spalte 3 und 13 in Spalte 5 usw.

Literatur

• Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June M. Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, Henk Van der Vorst: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. 2. Auflage. S. 57