imported>Aka: https, Kleinkram

2023-11-22T13:14:49Z

https, Kleinkram

Neue Seite

'''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 kB) 2. Auflage. S. 57

[[Kategorie:Numerische Mathematik]]

Compressed Row Storage - Versionsgeschichte

imported>Aka: https, Kleinkram