THIS IS A TEST INSTANCE. ALL YOUR CHANGES WILL BE LOST!!!!
- This page is for documentation and discussion of parallel algorithms on GPU for dot product involving sparse matrices.
- dot(dense, csr.T) = dense
- Lemma: csr.T is equivalent to interpreting the same csr input as a csc matrix
- Algorithm: Treat the input as a csc matrix, use one GPU thread per column, scan for every row in dense matrix, output to corresponding position in output dense matrix
- dot(dense, csr) = dense
- Take One: Transpose the right-hand side csr matrix (in parallel fashion), then apply the above algorithm
- Take Two: Change csr to coo through a histogrammming and exclusive scan on the indices vector of input csr, then sort all elements by column, then apply the above algorithm
- Take Three(flaky): One GPU thread per row on original input, for each element in the row, multiply by the corresponding element in the dense matrix, then atomically add to corresponding destination in output (flaky due to float32 additions do not obey commutative law).
...
- dot(csr.T, dense) = dense
- Transpose the lefthand side to it's csc form (in parallel fashion), then do the multiply-and-add for each element in the output matrix using a warp or single thread depending on the shape and size of the inputs.