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

J4 ›› 2013, Vol. 35 ›› Issue (11): 134-138.

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

许彬彬，戴清平，朱敏，谢端强

（国防科学技术大学理学院，湖南长沙 410073）

收稿日期:2013-06-14 修回日期:2013-10-11 出版日期:2013-11-25 发布日期:2013-11-25

Storage and computation of sparse
matrix based on Huffman coding

XU Bin-bin,DAI Qing-ping,ZHU Min,XIE Duan-qiang

(School of Science,National University of Defense Technology,Changsha 410073，China)

Received:2013-06-14 Revised:2013-10-11 Online:2013-11-25 Published:2013-11-25

摘要/Abstract

摘要：

在科学计算中，稀疏矩阵与向量乘积SMVP是一个十分重要的计算内核，它的效率主要是由稀疏矩阵的存储模式及相应的SMVP算法所决定。为了在稀疏矩阵的存储模式方面获得较好的性能，在哈夫曼压缩编码的基础上，对现有的分块压缩行存储BCRS方法进行了改进，在一定程度上减少了冗余零元素的存储，并且给出了与新的BCRS方法相对应的SMVP算法。理论分析和数据实验表明，基于哈夫曼压缩编码的BCRS方法在数据复杂度方面优于原始的两种BCRS方法。关键词：

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

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

许彬彬，戴清平，朱敏，谢端强. 基于哈夫曼编码的稀疏矩阵的存储与计算[J]. J4, 2013, 35(11): 134-138.

XU Bin-bin,DAI Qing-ping,ZHU Min,XIE Duan-qiang. Storage and computation of sparse
matrix based on Huffman coding [J]. J4, 2013, 35(11): 134-138.

[1]	王兆丽，肖春霞，王梅娟，蒋园园，董会. 哈夫曼编码在图像无损压缩中的应用[J]. 计算机工程与科学, 2019, 41(增刊S1): 200-202.
[2]	王波涛，李昂，陈月梅，邓诗卓，常博涵，吴俊学. H-PCPIR-V：基于Huffman编码的PCPIR-V优化算法[J]. 计算机工程与科学, 2018, 40(03): 418-430.