一种求解机组组合问题的内点半定规划GPU并行算法

摘要：

针对内点法求解机组组合问题的半定规划(SDP)模型时大规模线性方程组计算时间太长的问题,提出一种基于图形处理器(GPU)的Krylov子空间并行算法.该算法采用预条件处理的拟最小残差法(QMR法),并以矩阵分块技术为基础,在CSR存储格式下使用GPU实现Incomplete Cholesky并行预处理矩阵的计算.通过对不同规模线性方程组的计算分析表明,与传统的Cholesky直接法相比,QMR并行算法具有速度和存储优势,可获得良好的并行加速比.10～100机6个系统的仿真结果也表明,该SDP并行内点法在减少计算时间的同时可求得近似最优解.

关键词：机组组合、半定规划、GPU、QMR、不完全Cholesky分解、并行算法、Krylov、线性规划

所属期刊栏目：33

分类号：TM76(输配电工程、电力网及电力系统)

资助基金：国家高技术研究发展计划863计划资助项目2011-AA05A105;the National High Technology Research and Development Program of China863 Program2011-AA05A105

在线出版日期：2013-10-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：126-131,138