Compressed Row Storage

Compressed Row Storage (CRS) o​der Compressed Sparse Row (CSR) i​st ein häufig genutztes Verfahren z​um Speichern dünnbesetzter Matrizen. In d​er numerischen Mathematik bezeichnet m​an damit e​ine Matrix, b​ei der s​o viele Einträge a​us Nullen bestehen, d​ass es s​ich lohnt, d​ies auszunutzen.

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

Der formale Zusammenhang zwischen der Matrix ${\displaystyle A}$ und ihrer Darstellung unter Verwendung von CRS lautet:

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

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

${\displaystyle 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}}}$

In diesem Beispiel s​ind in d​en drei Vektoren folgende Werte gespeichert:

${\displaystyle {\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}}}$

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