| 引用本文: | 张宁宇,高 山,赵 欣.一种求解机组组合问题的内点半定规划GPU并行算法[J].电力自动化设备,2013,33(7): |
| ZHANG Ningyu,GAO Shan,ZHAO Xin.GPU parallel algorithm of interior point SDP for unit commitment[J].Electric Power Automation Equipment,2013,33(7): |
|
| 摘要: |
| 针对内点法求解机组组合问题的半定规划（SDP）模型时大规模线性方程组计算时间太长的问题，提出一种基于图形处理器（GPU）的Krylov子空间并行算法。该算法采用预条件处理的拟最小残差法（QMR法），并以矩阵分块技术为基础，在CSR存储格式下使用GPU实现Incomplete Cholesky并行预处理矩阵的计算。通过对不同规模线性方程组的计算分析表明，与传统的Cholesky直接法相比，QMR并行算法具有速度和存储优势，可获得良好的并行加速比。10~100机6个系统的仿真结果也表明，该SDP并行内点法在减少计算时间的同时可求得近似最优解。 |
| 关键词: 机组组合 半定规划 GPU QMR 不完全Cholesky分解 并行算法 Krylov 线性规划 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| GPU parallel algorithm of interior point SDP for unit commitment |
|
ZHANG Ningyu, GAO Shan, ZHAO Xin
|
|
School of Electrical Engineering，Southeast University，Nanjing 210096，China
|
| Abstract: |
| 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 memory. Simulative results of six systems of 10~100 units also show that，an approximate optimal solution can be obtained with less computing time by the SDP parallel interior point method. |
| Key words: unit commitment semidefinite programming GPU QMR Ｉncomplete Cholesky decomposition parallel algorithms Krylov linear programming |
