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

AbstractPreconditioning 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 7×.Keywords: linear programmingscaling techniquesGPUMATLABCUDA2010 AMS Subject Classifications:: 65F3590C0590C99 AcknowledgementsThe authors thank NVIDIA for its support through the Academic Partnership Program. Furthermore, the authors are indebted to the anonymous referees whose comments and suggestions have improved the quality of the final paper.