Parallel patterns: sparse matrix computation
An introduction to data compression and regularization
This chapter introduces the parallel sparse matrix-vector computation pattern. It starts with the basic concepts of sparse matrices as a data compaction technique. It then introduces a kernel based on Compressed Sparse Row (CSR) data storage for sparse matrices. The ELL format with data padding is then introduced as a regularization technique for reduced control divergence and improved memory coalescing. The COO format is further introduced, a complementary regularization technique to reduce padding overhead. Finally, the Jagged Diagonal Storage (JDS) format based on sorting is introduced to smooth out variation from one row ...