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

GPU parallel algorithm of interior point SDP for unit commitment

作　　者：张宁宇[1] 高山[1] 赵欣[1] 

机构地区：[1]东南大学电气工程学院,江苏南京210096

出　　处：《电力自动化设备》2013年第7期126-131,138,共7页Electric Power Automation Equipment

基　　金：国家高技术研究发展计划(863计划)资助项目(2011-AA05A105)~~

摘　　要：针对内点法求解机组组合问题的半定规划（SDP）模型时大规模线性方程组计算时间太长的问题，提出一种基于图形处理器（GPU）的Krylov子空间并行算法。该算法采用预条件处理的拟最小残差法（QMR法），并以矩阵分块技术为基础。在CSR存储格式下使用GPU实现Incomplete Cholesky并行预处理矩阵的计算。通过对不同规模线性方程组的计算分析表明，与传统的Ch01eskv直接法相比，QMR并行算法具有速度和存储优势．可获得良好的并行加速比。10-100机6个系统的仿真结果也表明，该SDP并行内点法在减少计算时间的同时可求得近似最优解。Because the time consumption is too heavy when the interior point algorithm is used to solve the SDP（SemiDefinite Programming） model of unit commitment, the Krylov subspace parallel algorithm based on GPU（Graphic Processing Unit） is proposed,which,based on the matrix sectioning technology and in CSR storage format,applies the preconditioned QMR（Quasi-Minimal Residual） method to calculate the parallel Incomplete Cholesky preconditioning matrix by GPU. Analysis of the calculations for linear equation sets of different sizes shows that,with better parallel speedup ratio,QMR parallel algorithm is superior to the traditional Cholesky direct method in speed and units also show that,an approximate optimal solution can be obtained with less computing time by the SDP parallel interior point method.

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

分 类 号：TM76[电气工程—电力系统及自动化]