基于哈夫曼编码的稀疏矩阵的存储与计算  

Storage and computation of sparse matrix based on Huffman coding

作　　者：许彬彬[1] 戴清平[1] 朱敏[1] 谢端强[1] 

机构地区：[1]国防科学技术大学理学院,湖南长沙410073

出　　处：《计算机工程与科学》2013年第11期134-138,共5页Computer Engineering & Science

摘　　要：在科学计算中,稀疏矩阵与向量乘积SMVP是一个十分重要的计算内核,它的效率主要是由稀疏矩阵的存储模式及相应的SMVP算法所决定。为了在稀疏矩阵的存储模式方面获得较好的性能,在哈夫曼压缩编码的基础上,对现有的分块压缩行存储BCRS方法进行了改进,在一定程度上减少了冗余零元素的存储,并且给出了与新的BCRS方法相对应的SMVP算法。理论分析和数据实验表明,基于哈夫曼压缩编码的BCRS方法在数据复杂度方面优于原始的两种BCRS方法。In scientific kernel, and its efficien rithm. For the sake of cy ob computing, Sparse Matrix Vector Product （SMVP） is an important calculation is mainly determined by the storage model and the corresponding SMVP algo- taining 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. Theoreti- cal analysis and experiments show that the new Huffman coding based BCRS method outperforms the two traditional BCRS methods in data complexity.

关 键 词：哈夫曼编码 分块压缩行存储 稀疏矩阵向量乘积 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]