基于稀疏技术的序列运算方法  

Sparse technology based computing of sequence operation theory

作　　者：徐玮[1] 康重庆[1] 夏清[1] 

机构地区：[1]清华大学电机工程与应用电子技术系,电力系统及发电设备控制和仿真国家重点实验室,北京100084

出　　处：《清华大学学报（自然科学版）》2011年第1期53-57,62,共6页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(50777031);新世纪优秀人才支持计划资助(NCET-07-0484)

摘　　要：序列运算过程中经常遇到稀疏序列之间的相互运算。针对序列运算的计算优化问题,该文首先分析了序列稀疏性的成因,并分析了序列运算理论中不同类型基本运算对于序列稀疏性的影响,同时给出了相应的计算结果序列的稀疏度估算公式。然后,根据序列与序列运算的特点,将稀疏技术应用于序列运算中,提出了通用存储方法与特征存储方法等2种稀疏序列存储技术。最后,利用算例对所提出的稀疏序列存储方法加以检验,采用稀疏技术后不同类型序列运算的时间开销均有不同程度的降低,特别是卷和、交积、并积与序除运算的计算时间下降为原来的6%~38%,算例结果表明了该文工作的正确性与应用价值。Sequence operations often involve calculations between sparse vectors.Optimization of such calculations is a key problem in sequence operation theory to improve the computational efficiency.The causes of sequence sparsity and the impact of different basic operations in sequence operation theory on the sequence sparsity were analyzed to develop sparsity estimation formulas for the resulting sequences.These sparse vector operations can be naturally applied in sequence operations.A common storage method and a feature storage method were developed based on the characteristics of sequences and sequence operations.Tests of the sparse storage and computation methods show that for basic operations,the sparse methods reduce the times for addition-type convolution,AND-type products,OR-type products and sequence division operations by 6% to 38% compared to the original methods.

关 键 词：序列运算理论 稀疏技术 运算方法 一维序列 

分 类 号：O211.9[理学—概率论与数理统计] TM744[理学—数学]