GPU加速不完全Cholesky分解预条件共轭梯度法

来源：计算机研究与发展杂志2015年第4期北京时间：

作者：陈尧,赵永华,赵慰,赵莲,

摘要：不完全Cholesky分解预条件共轭梯度(incompleteCholeskyfactorizationpreconditionedconjugategradient,ICCG)法是求解大规模稀疏对称正定线性方程组的有效方法.然而ICCG法要求在每次迭代中求解2个稀疏三角方程组，稀疏三角方程组求解固有的串行性成为了ICCG法在GPU上并行求解的瓶颈.针对稀疏三角方程组求解，给出了一种利用GPU加速的有效方法.为了增加稀疏三角方程组求解在GPU上的多线程并行性，提出了对不完全Cholesky分解产生的稀疏三角矩阵进行分层调度(levelscheduling)的方法.为了进一步提高稀疏三角方程组求解的并行性能，提出了在分层调度前通过近似最小度(approximateminimumdegree,AMD)算法对系数矩阵进行重排序、在分层调度后对稀疏三角矩阵进行层排序的方法，降低了分层调度过程中产生的层数，优化了稀疏三角方程组求解的GPU内存访问模式.数值实验表明，与利用NVIDIACUSPARSE实现的ICCG法相比，采用上述方法性能可以获得平均1倍以上的提升.

关键词：不完全Cholesky分解, 预条件, 共轭梯度法, 重排序, 图形处理器,