一种准对角矩阵的混合压缩算法及其与向量相乘在GPU上的实现

摘要

稀疏矩阵与向量乘(SpMV)属于科学计算和工程应用中的一种基本运算,其高性能实现与优化是计算科学的研究热点之一.在微分方程的求解过程中会产生大规模的稀疏矩阵,而且很大一部分是一种准对角矩阵.针对准对角矩阵存在的一些不规则性,提出一种混合对角存储(DIA)和行压缩存储(CSR)格式来进行SpMV计算,对于分割出来的对角线区域之外的离散非零元素采用CSR存储,这样能够克服DIA在不规则情况下存储矩阵的列迅速增加的缺陷,同时对角线采用DIA存储又能充分利用矩阵的对角特征,以减少CSR的行非零元素数目的不均衡现象,并可以通过调整存储对角线的带宽来适应准对角矩阵的不同的离散形式,以获得比DIA和CSR更高的压缩比,减小计算的数据规模.利用CUDA平台在GPU上进行了实验测试,结果表明该方法比DIA和CSR具有更高的加速比.