稀疏对称矩阵的LDLT分解在GPU上的高效实现

陈鑫峰，王武

1.中国科学院计算机网络信息中心，北京 100190

2.中国科学院大学，北京 100049

引 言

稀疏对称矩阵的LDLT分解对许多科学工程问题的有效求解非常重要。例如基于有限差分或有限元离散得到的稀疏线性系统，若采用迭代法难以奏效（迭代收敛很慢甚至不收敛）时，直接法LU分解便可有效解决问题。若矩阵具有对称性，则LU分解转化为LDLT分解。直接法分解过程计算开销较大，如何提高其性能尤为重要。直接法的步骤可分为符号分解、数值分解和三角求解，其中数值分解最耗时。目前在多核或众核上并行实现稀疏矩阵分解比较困难，因为分解过程中有较多的数据依赖和不规则数据访问，导致难以充分利用这些多核CPU或加速卡，加速效果不佳，甚至无法加速。

基于CPU+GPU的并行异构架构已成为当今高性能计算机和服务器的主流体系结构之一。在GPU上稠密矩阵的计算已经具备很高的性能，如CUDA的cuBLAS库[1]，因为稠密问题有利于高效内存访问和存取，以及向量化计算指令集的应用。由于非零元素分布不规则的稀疏方程组难以高效访存和向量化计算，无法充分利用GPU的计算资源实现高效求解。目前有很多适用于CPU的稀疏矩阵直接法求解器，比如SuperLU、MKL的PARDISO、MUMPS、UMFPACK、HSL[2]的MA57等，但是在GPU上有效实现稀疏矩阵分解的软件还很少。CUDA的cuSOLVER[3]还没有提供GPU上稀疏LU分解的接口。加州大学Peng等[4]开发了基于GPU的稀疏LU分解算法库GLU 3.0，并用于集成电路仿真。它的数值分解较快，但符号分解存在瓶颈。如何有效利用GPU计算能力提升稀疏矩阵分解的性能仍是需要研究的课题[5]。……