基于分块存储格式的稀疏线性系统求解优化

Optimization of solving sparse linear system based on blocked storage format

针对基于GPU求解大规模稀疏线性方程组进行了研究,提出一种稀疏矩阵的分块存储格式HMEC(hybrid multiple ELL and CSR)。通过重排序优化系数矩阵的存储结构,将系数矩阵以一定的比例分块存储,采用ELL与CSR存储格式相结合的方式以适应不同的分块特征,分别使用适用于不对称矩阵的不完全LU分解预处理BiCGStab法和对称正定矩阵的不完全Cholesky分解预处理共轭梯度法求解大规模稀疏线性系统。实验表明,应用HMEC格式存储稀疏矩阵并以调用GPU kernel的方式实现前述两种方法,与其他存储格式的实现方式作比较,最优可分别获得31.89%和17.50%的加速效果。

This paper proposed a storage format HMEC(Hybrid Multiple ELL and CSR)of sparse matrix to solve large sparse linear equations on GPU.Firstly,it optimized the storage structure of the coefficient matrix by reordering.Secondly,it stored the coefficient matrix in a certain scale block.Then it adopted an approach by combining ELL and CSR storage format to adapt to different characteristics of blocks.At last,it took bi-conjugate gradient stabilized(BiCGStab)and conjugate gradient(CG)iterative methods to solve large sparse linear systems,they were respectively preconditioned by incomplete-LU and incomplete-Cholesky factorization for asymmetric and symmetric positive definite linear matrices.Experiments show that comparing the way by storing sparse matrices in HMEC format with other ways by storing in the common storage format,the acceleration of the best available it can get are 31.89%and 17.50%.