Abstract: Sparse matrix-vector multiplication(SpMV) is of singular importance in sparse linear algebra,which is an important issue in scientific computing and engineering practice．Much effort has been put into accelerating the SpMV and a few parallel solutions have been proposed．In this paper we focused on a special SpMV,sparse quasi-diagonal matrix multiplication(SQDMV)．The sparse quasi diagonal matrix is the key to solve many differential equation and very little research is done on this field．We discussed data structures and algorithms for SQDMV that were efficiently implemented on the CUDA platform for the fine-grained parallel architecture of the GPU．We presented a new diagonal storage format HDC,which overcomes the inefficiency of DIA in storing irregular matrix and the imbalances of CSR in storing non-zero element．Further,HDC can adjust the storage bandwidth of the diagonal to adapt to different discrete degree of sparse matrix,so as to get higher compression ratio than the DIA and CSR,reduce the computation complexity．Our implementation in GPU shows that the performance of HDC is better than other format especially for matrix with some discrete points outside the main diagonal．In addition,we combined the different parts of HDC to a unified kernel to get better compress ration and higher speedup ratio in GPU．

Key words: GPU,Sparse matrix,SpMV,CUDA