A computational comparison of scaling techniques for linear optimization problems on a graphical processing unit

作者：Ploskas Nikolaos; Samaras Nikolaos^*

来源：International Journal of Computer Mathematics, 2015, 92(2): 319-336.

DOI：10.1080/00207160.2014.890716

• MATLAB
• CUDA
• scaling techniques
• linear programming
• GPU
• 90C05
• 90C99
• 65F35

Preconditioning techniques are important in solving linear problems, as they improve their computational properties. Scaling is the most widely used preconditioning technique in linear optimization algorithms and is used to reduce the condition number of the constraint matrix, to improve the numerical behavior of the algorithms and to reduce the number of iterations required to solve linear problems. Graphical processing units (GPUs) have gained a lot of popularity in the recent years and have been applied for the solution of linear optimization problems. In this paper, we review and implement ten scaling techniques with a focus on the parallel implementation of them on GPUs. All these techniques have been implemented under the MATLAB and CUDA environment. Finally, a computational study on the Netlib set is presented to establish the practical value of GPU-based implementations. On average the speedup gained from the GPU implementations of all scaling methods is about 7x.

• 出版日期2015-2-1