CODEWITHSUNDEEP
matrixsparse-matrix
vsx06
vsx06

Reputation: 87

Sparse Matrices Storage formats - Conversion

Is there an efficient way of converting a sparse matrix in Compressed Row Storage(CRS) format to Coordinate List (COO) format ?

Upvotes: 2

Views: 2080

Answers (1)

Daniel Shapero
Daniel Shapero

Reputation: 1889

Have a look at Yousef Saad's library SPARSKIT -- he has subroutines to convert back and forth between compressed sparse row and coordinate formats, as well as several other sparse matrix storage schemes.

Anyhow, to see how to get the coordinate format from the compressed one, it's easiest to consider how you could have come up with the compressed row format in the first place. Say you have a sparse matrix in COO, where you've put everything in order, for example

rows: 1  1  1  1  2  2  2  2  2  3  3  3 ...
cols: 1  3  5  9  2  3  7  9  11 1  2  3 ...

So the non-zero entries in row 1 are (1,1), (1,3), (1,5), (1,9) and so forth. You're storing a lot of redundant data in the array of rows; you can instead just have an array ia such that ia(i) tells you the starting address in the array cols for row i. In our example above, we would then have

ia  : 1  5  10  ...
cols: 1  3  5  9  2  3  7  9  11 1  2  3 ...

To go from COO to CSR, we just use the fact that

ia(i+1) = ia(i) + number of non-zero entries in row i

for any i. Knowing that, you can work backwards to get the COO format from CSR.

Upvotes: 2

Related Questions