Saturday, October 1, 2011

Compressed Row Storage (CRS)

The Compressed Row Storage format is the most general way to compress a matrix, since it makes absolutely no assumptions about the sparsity structure of the matrix, and it doesn't store any unnecessary elements.

CRS store matrix in the {val, col_ind, row_ptr} format, where val, col_ind and row_ptr are explained below:

  • val: vector stores the values of the nonzero elements of the matrix in a row-wise order.
  • col_ind: vector stores the column indexes of the elements in the val vector.
  • row_ptr: vector stores the locations in the val vector that start a row.
A quick example, matrix A = 
| 7  0  0  2 |
| 0  2  0  4 |
| 1  0  0  0 |
| 3  8  0  6 |
val = [7 2 2 4 1 3 8 6]
col_ind = [1 4 2 4 1 1 2 4]
row_ptr = [1 3 5 6 9]

Covert a matrix A to CSR format in MATLAB, first set A = A' and then run following codes:
[col_ind row_ind val] = find(A);
[row col] = size(A);
val = zeros(1,length(row_ind));
row_ptr = zeros(1,row+1);
row_ptr(1)=1;
row_ptr(row+1)=length(row_ind)+1;
l = 2;
row_ind_temp = row_ind(1);
for i=1:length(row_ind)
    val(i)=A(row_ind(i),col_ind(i));
    if row_ind(i)~=row_ind_temp
        row_ptr(l)=i;
        l=l+1;
        row_ind_temp=row_ind(i);
    end
end

No comments:

Post a Comment