一种基于图形处理器的压缩单纯形方法

针对GPU通用计算环境CTM纹理资源的限制,研究了一种适于CTM的单纯形方法.依据单纯形方法每次变换最多只增加一列非单位元向量和矩阵求逆运算的特征,给出GPU上系数矩阵、基逆矩阵等的压缩存储策略及在该策略下求解基逆矩阵、单纯形乘子和检验数等步骤新的计算规则.CPU主要进行迭代控制;而计算密集类任务皆由GPU完成.理论分析证明该方法比标准方法在时空复杂度上提高了一个数量级.数值实验表明该方法不仅扩大了可求解问题的规模,且在获得正确优化结果的前提下,效率比CPU版本有数百倍的提高,甚至数倍领先于MATLABR2007a.