Assumptions in abstract sparse array interface

[gdalle]

To fully harmonize formats, we need to specify:

• In CSC/CSR, whether the indices are sorted or not within each column/row
  • CUDA: not necessarily
  • AMDGPU: yes
• In COO, whether the coefficients are sorted and how
  • CUDA: sorted by row but not necessarily by column inside each row
  • AMDGPU: sorted by row and then by column inside each row
• In all formats, whether index duplicates are allowed
  • CUDA: no
  • AMDGPU: no
• Whether the interpretation of BSR is the same (this seems like a spot where backend variation is expected)

If we go for the strict option and the CUDA input doesn't satisfy the sorting assumptions, we need to error or perform a sorting step.

Useful table with links to backend docs: albertomercurio/GenericSparseArrays.jl#8

Related: JuliaGPU/CUDA.jl#2942

[gdalle]

@kshyatt giving this some more thought, I reached a very simple conclusion:

1. CUDA's types allow unsorted indices
2. We want CUDA's types to be subtypes of the abstract types defined here (Try integrating with the GPUArrays sparse migration CUDA.jl#2942)
3. Therefore the abstract types defined here must allow unsorted indices
4. This means every occurrence of searchsortedfirst in https://github.com/JuliaGPU/GPUArrays.jl/blob/master/src/host/sparse.jl must be replaced by findfirst

[kshyatt]

Nice, thanks for taking a look. Want to make the PR?