clarify mkl-sparse-sort

[sycl-developer]

Please clarify which value(s) are sorted by the function https://www.intel.com/content/www/us/en/docs/onemkl/developer-reference-dpcpp/2023-1/oneapi-mkl-sparse-sort-matrix.html ?

Thanks

[Gajanan_Choudhary]

Hi,

The oneapi::mkl::sparse::sort_matrix() documentation says:

The oneapi::mkl::sparse::sort_matrix API performs in-place sorting of user-provided sparse matrix arrays stored in a given sparse matrix handle.

---

For CSR matrices that are currently the only supported matrix format, this means that it sorts the user-provided column indices and values arrays of the CSR matrix for each row of the matrix. By "user-provided", we mean the user data stored in the matrix handle through the oneapi::mkl::sparse::set_csr_data() API call.

Hope that helps!

Regards,

Gajanan

[Spencer_P_Intel]

To expand a little on Gajanan's great answer.  The user-provided data in the matrix handle is what is "sorted"; how it is sorted is based on the particular matrix format setup in the handle.  For instance, for CSR format, the colind and values arrays are sorted by smallest to largest column index subordinate to each row.  That is, it is essentially a batched sort function that sorts colind/value pairs on each "row" by colind values. Most sparse format have at least one "natural" concept of sortedness, with COO format having two that are "natural" (by column or by row). There are some which it is more difficult to define what is meant by sorted (think of an ELLPACK matrix where it is squished to the left, backfilled and then stored in a column major format -- sortedness is a "strided" kind of sorted in that case where it is again sorted on each row, even though the data is not stored contiguously on rows..) As different formats get added, we will try to be more specific in our documentation about what sort_matrix() means for that particular format :).

By the way, this is one of the few sparse blas functions that will modify user-provided data in the matrix handle and it's existence as an API is one of the reasons we don't have const properties on the provided matrix arrays in sparse::set_csr_data().  Our general policy is to not modify user-provided data in the matrix_handle unless the API being called explicitly says that it modifies it.

Spencer

[sycl-developer]

"It is essentially a batched sort function that sorts colind/value pairs on each "row" by colind value". 

Then, is there an oneMKL function that sorts the values ?  I think the values can be sorted in cuSparse.

Thanks again. 

[Spencer_P_Intel]

no, there is no such onemkl sparse function that would sort based on values -- only sorting of matrix based on column indices.  You could look into onedpl for a general sort function (for instance oneapi::dpl::sort_by_key) for an array or pair of arrays that could do this, but the batched part would be more of a challenge, since you are still wanting to sort within each row, right ?

May I ask, what is the purpose of sorting a matrix by values?  In my mind, it is not a common thing to do for linear algebra or sparse algorithms, so I am curious to understand what it might be useful for

Spencer

[Gajanan_Choudhary]

@Spencer_P_Intel , I believe they meant sorting the values, not sorting by values:

is there an oneMKL function that sorts the values ?

---

@sycl-developer, sort_matrix sorts both column indices and values together. The sorting happens by column indices for each row, and the values are associated to those column indices. In short, oneapi::mkl::sparse::sort_matrix() is the equivalent of cusparseXcsrsort() function from cuSPARSE for CSR matrix format.

[sycl-developer · Accepted solution]

Thank you all for your answers and suggestions !  I thought the cusparseXcrsort() function sorts the values in a matrix by row. So a function equivalent to the CUDA function may be helpful. However,  Gajanan mentioned that "oneapi::mkl::sparse::sort_matrix() is the equivalent of cusparseXcsrsort() function".

[Gajanan_Choudhary]

For the sake of others landing here, allow me to add an example of what oneapi::mkl::sort_matrix() does:

Consider a dense matrix with 6 non-zero values:

         | 0  c  0  0 |
denseA = | a  0  e  0 |
         | b  d  0  f |

Here's an example of an unsorted CSR matrix representation of the above dense matrix in 0-based indexing:

                     |<r1>|<--r2-->|<---r3--->|
sortedCsrARowPtr   = [ 0  |  1     |  3       | 6 ] <- Always sorted by definition
unsortedCsrAColInd = [ 1  |  2  0  |  3  0  1 ]     <- Unsorted
unsortedCsrAValues = [ c  |  e  a  |  f  b  d ]     <- Unsorted, associated to colInd

Here's how the unique sorted representation of the above CSR matrix looks like, which is what oneapi::mkl::sort_matrix() would give in-place, modifying the user data in the matrix handle:

                     |<r1>|<--r2-->|<---r3--->|
sortedCsrARowPtr   = [ 0  |  1     |  3       | 6 ] <- Always sorted by definition
sortedCsrAColInd   = [ 1  |  0  2  |  0  1  3 ]     <- Sorted
sortedCsrAValues   = [ c  |  a  e  |  b  d  f ]     <- Sorted, associated to colInd

[sycl-developer]

I copy and paste the CUDA function:

"This function sorts CSR format. The stable sorting is in-place.

The matrix type is regarded as CUSPARSE_MATRIX_TYPE_GENERAL implicitly. In other words, any symmetric property is ignored.

This function csrsort() requires buffer size returned by csrsort_bufferSizeExt(). The address of pBuffer must be multiple of 128 bytes. If not, CUSPARSE_STATUS_INVALID_VALUE is returned.

The parameter P is both input and output. If the user wants to compute sorted csrVal, P must be set as 0:1:(nnz-1) before csrsort(), and after csrsort(), new sorted value array satisfies csrVal_sorted = csrVal(P). "

[VarshaS_Intel]

Hi,

Thanks for posting in Intel Communities.

>>Thank you all for your answers and suggestions

It's great to know that your issue is resolved, in case you run into any other issues please feel free to create a new thread.

Have a Good Day!

Thanks & Regards,

Varsha