Mixed-Precision Parallel Linear Programming Solver

• Mujahed Eleyat Miriam AS
• Lasse Natvig Norwegian University of Science and Technology

Abstract

We use mixed-precision technique, which is used to exploit the high single precision performance of modern processors, to build the first sparse mixed-precision linear programming solver on the Cell BE processor. The technique is used to enhance the performance of an LP IPM-based solver by implementing mixed-precision sparse Cholesky factorization, the most time consuming part of LP solvers. Moreover, we implemented sparse matrix multiplication of the form required by the solver as it is also very time consuming for some LP problems. Implemented on the Cell BE processor (Playstation 3) and tested using Netlib data sets, our LP solver achieved a maximum speedup of 2.9 just by using the mixed-precision technique. Moreover, we found that some problems, especially in final iterations, result in ill-conditioned matrices where mixed-precision can not be used. As a result, the solver needs to switch to double-precision if a more accurate solution of an LP problem is required.

Keywords: Program processors, Sparse matrices, Linear programming, Computer architecture, Accuracy, Acceleration, Indexes, Mixed-precsision, Cholesky factorization, Cell BE processor, Linear Programming