Quelltext der Seite Compressed Row Storage

'''Compressed Row Storage''' (CRS) oder '''Compressed Sparse Row''' (CSR) ist ein häufig genutztes Verfahren zum Speichern [[Dünnbesetzte Matrix|dünnbesetzter Matrizen]]. In der [[Numerische Mathematik|numerischen Mathematik]] bezeichnet man damit eine [[Matrix (Mathematik)|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:<br />
(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: [https://netlib.org/templates/templates.pdf ''Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods.''] (PDF; 762&nbsp;kB) 2. Auflage. S. 57

[[Kategorie:Numerische Mathematik]]