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

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

<math>A_{i,j} =val[k] \iff (colInd[k] = j ) \land ( rowPtr[i] \leq k < rowPtr[i+1] ).</math>

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

<math>A=

 \begin{pmatrix} 
   \underset{({\color{Blue}0},{\color{Green}0})}{10} & 0 & 0 & \underset{({\color{Blue}0},{\color{Green}3})}{12} & 0 \\ 
   0 & 0 & \underset{({\color{Blue}1},{\color{Green}2})}{11} & 0 & \underset{({\color{Blue}1},{\color{Green}4})}{13} \\
   0 & \underset{({\color{Blue}2},{\color{Green}1})}{16} & 0 & 0 & 0 \\
   0 & 0 & \underset{({\color{Blue}3},{\color{Green}2})}{11} & 0 & \underset{({\color{Blue}3},{\color{Green}4})}{13} \\
 \end{pmatrix}

</math>

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

<math>

 \begin{matrix}
   val & =
     & \left( \underset{({\color{Blue}0},{\color{Green}0})}{10} \right.
     &        \underset{({\color{Blue}0},{\color{Green}3})}{12}
     &        \underset{({\color{Blue}1},{\color{Green}2})}{11}
     &        \underset{({\color{Blue}1},{\color{Green}4})}{13}
     &        \underset{({\color{Blue}2},{\color{Green}1})}{16}
     &        \underset{({\color{Blue}3},{\color{Green}2})}{11}
     & \left. \underset{({\color{Blue}3},{\color{Green}4})}{13} \right)
     \\
   colInd & =
     & \left( \underset{({\color{Blue}0}\,}{{\color{Green}0}} \right.
     &        \underset{\ \,)}             {{\color{Green}3}}
     &        \underset{({\color{Blue}1}\,}{{\color{Green}2}}
     &        \underset{\ \,)}             {{\color{Green}4}}
     &        \underset{({\color{Blue}2}) }{{\color{Green}1}}
     &        \underset{({\color{Blue}3}\,}{{\color{Green}2}}
     & \left. \underset{\ \,)}             {{\color{Green}4}} \, \right)
     \\
   rowPtr & =
     & \left( \underset{({\color{Blue}0})}{0} \right.
     &        \underset{({\color{Blue}1})}{2}
     &        \underset{({\color{Blue}2})}{4}
     &        \underset{({\color{Blue}3})}{5}
     & \left. \underset{({\color{Blue}4})}{7} \right)
     &
     &
 \end{matrix}

</math> Sowohl <math>val</math> als auch <math>colInd</math> enthalten 7 Elemente, dies entspricht immer der Anzahl der Nichtnullelemente in <math>A</math>. <math>rowPtr</math> hat 5 Elemente; die Anzahl der Elemente ist immer um 1 größer als die Anzahl der Zeilen von <math>A</math>. Das Element 0 hat den Wert 0, das letzte Element gibt die Größe von <math>colInd</math> 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 <math>rowPtr</math> zeigen an, dass an der Stelle 2 der Vektoren <math>val</math> und <math>colInd</math> 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 <math>colInd</math>, ihre Werte an den entsprechenden Stellen in <math>val</math>: 11 in der Spalte 2 und 13 in der Spalte 4.

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. (PDF; 762 kB) 2. Auflage. S. 57