CSR vs CSC sparse encoding

[jim22k]

Nearly everyone who has worked on mlir-graphblas has fallen into the trap of assuming that dimLevelType determines CSR vs CSC format. This is not the case. Instead, dimOrdering is what differs between CSR and CSC.

#CSR = #sparse_tensor.encoding<{
  dimLevelType = [ "dense", "compressed" ],
  dimOrdering = affine_map<(i,j) -> (i,j)>,
  pointerBitWidth = 64,
  indexBitWidth = 64
}>

#CSC = #sparse_tensor.encoding<{
  dimLevelType = [ "dense", "compressed" ],
  dimOrdering = affine_map<(i,j) -> (j,i)>,
  pointerBitWidth = 64,
  indexBitWidth = 64
}>

To explain what dimLevelType does, let's consider a simple 3x3 sparse matrix. We will represent this data using 4 different dimLevelTypes, but always in row-wise ordering.

    0  1  2
   ---------
0 | .  1  2
1 | .  .  . 
2 | .  3  4

Dense Format

#DENSE = #sparse_tensor.encoding<{
  dimLevelType = [ "dense", "dense" ],
  dimOrdering = affine_map<(i,j) -> (i,j)>,
  pointerBitWidth = 64,
  indexBitWidth = 64
}>
pointers = ([], [])
indices = ([], [])
values = [0, 1, 2, 0, 0, 0, 0, 3, 4]

CSR Format

#CSR = #sparse_tensor.encoding<{
  dimLevelType = [ "dense", "compressed" ],
  dimOrdering = affine_map<(i,j) -> (i,j)>,
  pointerBitWidth = 64,
  indexBitWidth = 64
}>
pointers = ([], [0, 2, 2, 4])
indices = ([], [1, 2, 1, 2])
values = [1, 2, 3, 4]

Block Sparse (?) format
This contains dense values, but only for rows with at least 1 value

#BLOCKS = #sparse_tensor.encoding<{
  dimLevelType = [ "compressed", "dense" ],
  dimOrdering = affine_map<(i,j) -> (i,j)>,
  pointerBitWidth = 64,
  indexBitWidth = 64
}>
pointers = ([0, 2], [])
indices = ([0, 2], [])
values = [0, 1, 2, 0, 3, 4]

HyperSparse or Doubly Compressed

#DCSR = #sparse_tensor.encoding<{
  dimLevelType = [ "compressed", "compressed" ],
  dimOrdering = affine_map<(i,j) -> (i,j)>,
  pointerBitWidth = 64,
  indexBitWidth = 64
}>
pointers = ([0, 2], [0, 2, 4])
indices = ([0, 2], [1, 2, 1, 2])
values = [1, 2, 3, 4]

[eriknw]

I would call ["compressed", "dense"] CDR (CDC) for "Compressed Dense Row (Column)". This is not standard notation. I don't think this format has a common name. "Block Sparse" means something else.