CSR matrix compression

[JWagner]

Hello everyone,

I am working with sparse matrices in csr format, since I assumed that they  would be more memory efficient that the coo format. During my setup phase I am multiplying my csr-format matrix with a scalar matrix which also sets a few rows to zero. Currently I am debugging the result and use the export function to have a look into the arrays of value, row, column, etc. I recognized that entries that turned zero through the multiplication before are still existing. Since it is the big advantage of csr that only non-zero values are storred I was wondering if there is any way to discard all zero entries (compress the matrix)? Btw. the entries in row_start  & column_indx are also still pointing to entries in the value array that are zero.

Regards.

[mecej4]

A compact representation of a sparse matrix reduces the memory footprint of the matrix, but using such a representation places restrictions on how the matrix elements are accessed. With the CSR representation that is used in MKL, accessing all the elements of a given row can be done efficiently. On the other hand, if you want to locate the diagonal element of a specified row, you will have to do a linear or binary search of the entries for the row. 

Similarly, it is quite expensive and inconvenient to remove existing elements or to add new elements and maintain compactness. If you need to perform a large number of updates to the shape of a matrix, the commonly used representations such as CSR, COO, etc., may not be suitable.

[JWagner]

Hi mecej4,

Thank you for your reply. Since it is also part of my code, I am aware that changing values in a matrix is a rather time consuming operation. But this is not the issue. I also don't have to perform a large number of updates to the shape of the matrix. I have a setup phase in which my matrix gets assembled, therefore I only need to perform it once and if it is expencive, I can live with it (of course until a certain degree).

Perhaps it is better if I give an example:

I have the scaling matrix (sparse in csr format) A =[2,0,0; 0, 0,0;  0,0,2] and the sparse matrix in csr format B = [1 , 0, 0; 0, 0, 1; 0, 0, 1]. The letter would have these three (zero-based) arrays:

values[] = {1,1,1},  row_start[]={0,1,2}, col_indx[] = {1,2,2} (let's ignore the row_end for this example and stick to the classical 3-Array CRS)

If I calculate the product of A and B via mkl_sparse_sp2m the result will be: [2,0,0; 0,0,0;  0,0,2]. If I export the componenses of the matrix handle via mkl_sparse_d_export_csr I get: values[] = {1,0,1},  row_start[]={0,1,2}, col_indx[] = {1,2,2}.

Since my matrices are much bigger, the amount of zero entries in the multiplication result are more and the resulting matrix is heavily used, it would be nice to have ANY kind of way to get rid of these entries.

[mecej4]

A "scalar matrix" is, by convention/definition a multiple of the identity matrix, i.e., λI, a diagonal matrix with all the diagonal elements equal to λ .

Your usage of "scalar" does not follow this convention, since you allow the second diagonal entry of your 3 X 3 "scalar matrix" to be zero. 

A more serious issue is that a matrix row with all zeros is not the same as an absent row. If you squeezed out row-2 of your example, which has all zeros, what is left would be a 2 X 3 matrix, and you would not know any more whether the removed row was row-1, row-2 or row-3 in the original matrix.

You may have noticed that many sparse matrix routines require that in such cases the zero-valued diagonal entry is retained in the CSR or other sparse-matrix representation, for this very reason. Thus, values = {2,0,2} cannot be squeezed down to {2,2},  and the '0' place-holder cannot be omitted.

You could probably develop a consistent convention for your own portions of the code, such as "if the row-start index values imply a missing row, it is the last row of the original matrix that was dropped", but library routines would probably not be able to do the same.

[JWagner]

Thank you for the clarification mecej4, you were a great help. I suspected as much but I wanted to be sure, before I implement something by myself.

[Spencer_P_Intel · Accepted solution]

Hi JWagner,

So it is a good question about whether we have a compression function in MKL.  As mecj4 explained very well, we do not in our library trim the sparsity pattern to get rid of "zero" elements.  There are several reasons for this, the first being that with floating point operations, it is hard to determine whether something is actually zero or just really small.  We would need to introduce some sort of callback function or thresholding value that the user can set to say when something is actually "zero" and should be removed.  Second, we have not had anyone actually request this feature.    It would not be very hard to create one for yourself, especially if it is not a frequent operation and not on a hot part of your algorithm.

Pseudo code for the operation in-place:  Start from the beginning of your vals/col_ind arrays, keeping track of latest element in compressed array, and latest element in current array (both pointing into the same memory chunks).  If the latest element is "zero", just increment the latest element being processed, otherwise copy over...  (I guess you could do it in two steps,  one in parallel compressing each row and updating counts in row_start to reflect number of non zeros on the row, then in second pass, copy over chunks of row data, adding up row_start to be increasing again).  If you are doing it yourself,  export the arrays from the C matrix handle,  then destroy the handle, do your operations on the arrays, then create a new handle with updated values... (We have an implicit agreement that user will not modify the arrays while they are in a matrix handle, and we will not modify the users data arrays unless explicitly done through an API that says it will do so (sorting, conversion, set values, etc  as in IE Sparse BLAS Matrix Manipulation Routines  )  (for out-of-place, you can after the first pass know how much memory is needed, allocate it, then copy into the new arrays...)

So it turns out that the CSR format can actually support empty rows just fine.  For the 3 array CSR format, I like to think of the row_start array as denoting half open intervals in col_ind and vals arrays of the type [start of row_i, one past end of row i) extracted in the form of [row_start[i], row_start[i+1]).  Thus if the first row (0 base) were empty, then row_start array could look like {0, 0, 4 ...}   and the first row interval would be [0,0)  ie empty.  Of course this could be done at any row and row_start having two entries with the same value denotes that row is empty...  What we can't do is compress the row_start array to be shorter than num_rows+1 in the CSR format.

Ex: C = [2,0,0; 0,0,0; 0,0,2]  can be written as 
nrows = 3, num_cols = 3, nnz = 2

row_start[] = {0,1,1,2}  (or row_start[] = {0, 1, 1},  row_end[] = {1, 1, 2}  )

col_ind[] = {0,2}

vals[] = {2, 2}

There is a sparse matrix format out there that allows to compress row_start array (it essentially treats row_start as a sparse vector) called the hypersparse CSR format.  It regularly comes up in graph algorithms, but we do not currently support it in our library.

[JWagner]

Thank you Spencer for the very nice explanation, I think I know how to proceed from here on. Really great help!

[ArpitaP_Intel]

Hi Jwagner,

Glad to know that your issue is resolved. If you need any additional information, please submit a new question as this thread will no longer be monitored.

Regards,

Arpita