电子学报2009，Vol.37Issue(11)：2574-2578,5.
一种基于图形处理器的压缩单纯形方法
A Compressed Simplex Method Based on GPU
摘要
Abstract
We present a GPU-based algorithm for solving linear programming problems using simplex methods under CTM ( close to the metal) environment. Matrix-packed storage strategy and correlative computation formulas such as revised basic matrix? simplex multiplier and departing variables are brought forward, according to the fact that at most one column vector produces in each vertex changing step and the feature of reverse matrix of simplex method.CPU takes charge of the iteration and all compute-inten-sive tasks are carried out by GPU.Theory analysis proves that both space complexity and time complexity are superior to traditional method.Numerical experiments on randomly generated problems demonstrate that this method can not only get correct optimal solution, but also reach as fast as hundred times of CPU-based version; and it runs several times faster than MATLAB R2007a.关键词
单纯形方法/图形处理器/CTM/纹理/像素程序Key words
simplex method/ graphics processing unit/ close to the metal/ texture/ pixel shader分类
信息技术与安全科学引用本文复制引用
白洪涛,欧阳丹彤,何丽莉,姜珊珊..一种基于图形处理器的压缩单纯形方法[J].电子学报,2009,37(11):2574-2578,5.基金项目
国家自然科学基金重大项目(No.60496320 （）
No.60496321) （）
国家自然科学基金(No.60773097,No.60873148) （No.60773097,No.60873148）
