Compressed row storage

Compressed Row Storage (CRS) or Compressed Sparse Row (CSR) is a frequently used method for storing sparse matrices . In numerical mathematics , this is used to describe a matrix in which so many entries consist of zeros that it is worthwhile to take advantage of this.

With the CRS method, only the non-zero entries of a matrix are stored: In the form of an array , i.e. at successive locations in the memory. The information required for mapping between positions in the matrix and the array is stored in two further arrays and . The index of its column is stored in for each entry . It therefore includes as many elements as . The values ​​in determine which values belong to which row. ${\displaystyle (m\times n)}$ ${\displaystyle A}$ ${\displaystyle val}$ ${\displaystyle val}$ ${\displaystyle rowPtr}$ ${\displaystyle colInd}$ ${\displaystyle colInd}$ ${\displaystyle val}$ ${\displaystyle val}$ ${\displaystyle rowPtr}$ ${\displaystyle val}$

The formal relationship between the matrix and its representation using CRS is: ${\displaystyle A}$

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

Example:
(The blue numbers indicate the rows and the green numbers the columns of the matrix . As usual in many computer languages, the indices begin with 0.) ${\displaystyle A}$

${\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 this example, the following values ​​are stored in the three vectors:

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

Both and contain 7 elements, this always corresponds to the number of non-zero elements in . has 5 elements; the number of elements is always 1 greater than the number of lines of . Element 0 has the value 0, the last element indicates the size of , in this case 7. ${\displaystyle val}$ ${\displaystyle colInd}$ ${\displaystyle A}$ ${\displaystyle rowPtr}$ ${\displaystyle A}$ ${\displaystyle colInd}$

Line 1 of the matrix is ​​reconstructed from the compressed memory form as follows: Elements 1 and 2 of the vector indicate that the following line begins at position 2 of the vectors and row 1 and position 4. Line 1 has two elements different from 0. Their column indices are in positions 2 and 3 of , their values ​​in the corresponding positions in : 11 in column 2 and 13 in column 4. ${\displaystyle rowPtr}$ ${\displaystyle val}$ ${\displaystyle colInd}$ ${\displaystyle colInd}$ ${\displaystyle val}$

literature

• 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) 2nd edition. P. 57