Efficient strategy for compressing sparse matrices on Graphics Processing Units

Sparse matrix is used in a large number of important application codes, such as molecular dynamics, finite element methods, path problems, and etc. Much research has proposed several techniques to improve the performance for the sparse matrix operations based on the Graphic Processing Unit (GPU). However, there is no efficient method for compressing sparse matrix on GPU. Hence, in this paper, we design a strategy to efficiently compress sparse matrices based on the concept of GPU. Moreover, we discover the compressing sparse matrix problem that runs on the GPU could encounter some prefix sum problems under the SIMT architecture. We further propose two other types of prefix sum, horizontal prefix sum (HPS) and vertical prefix sum (VPS) in order to solve the compressing sparse matrix problem on GPU.