A compressed simplex method based on GPU

作者：Bai Hong Tao^*; Ouyang Dan Tong; He Li Li; Jiang Shan Shan

来源：Acta Electronica Sinica, 2009, 37(11): 2574-2578.

• Basic matrices
• Changing step
• Column vector
• Compute-intensive tasks
• GPU-based algorithms
• Graphics Processing Unit
• Linear programming problem
• matrix
• Numerical experiments
• Optimal solutions
• Pixel shader
• Simplex method
• Simplex methods
• Space complexity
• Time complexity

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-intensive 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.

• 出版日期2009