基于GPU的SSOR稀疏近似逆预条件研究

Research of the SSOR sparse approximate inverse preconditioner on GPUs

由于SSOR预条件共轭梯度算法中预条件方程求解需要前推和回代,导致算法迁移到GPU平台上并行效率不高.为此,基于诺依曼多项式分解技术,提出了一种GPU加速的SSOR稀疏近似逆预条件子(GSSORSAI).它不仅保持了原线性系统系数矩阵的稀疏和对称正定特性,而且预条件方程求解仅需一次稀疏矩阵矢量乘运算,避免了前推和回代过程.实验结果表明:在NVIDIA Tesla C2050GPU上,对比使用Python在单个CPU上SSOR稀疏近似逆预条件子实现方法,GSSORSAI平均快将近100倍;应用到并行的PCG算法中,相比无预条件的CG算法,平均提高了算法的3倍的收敛速度.

For the SSOR preconditioned conjugate gradient algorithm,the preconditioner equation solving needs the forward/backward substitutions,which greatly prevents parallelizing SSOR PCG algorithms on the GPU platform due to their strong serial processing.Thus,based on the Neumann series approximation, a GPU accelerated SSOR sparse approximate inverse preconditioner is proposed.For GSSORSAI,it preserves the sparse and symmetric positive characteristics of the original coefficient matrix in the linear system,and the preconditioner equation solving only needs a sparse matrix-vector multiplication operation,which avoids the forward/backward substitutions.Experiments results show on the NVIDIA Tesla C2050 GPU,GSSORSAI is generated on average 100 times faster than the implementation by Python on single CPU.Compared to the convergence of the CG algorithm,the PCG algorithm with GSSORSAI has on average 3times faster convergent rate.