Abstract:

In scientific computing, Sparse Matrix Vector Product (SMVP) is an important calculation kernel, and its efficiency is mainly determined by the storage model and the corresponding SMVP algorithm. For the sake of obtaining better performance in the storage model of sparse matrix, based on the Huffman coding, we optimize the BCRS(Block Compressed Row Storage) method so as to reduce the storage of redundant zeros to some extent. And propose the corresponding SMVP algorithm. Theoretical analysis and experiments show that the new Huffman coding based BCRS method outperforms the two traditional BCRS methods in data complexity.

Key words: Huffman coding;block compressed row storage;sparse matrix vector product