GPU Predictor-Corrector Interior Point Method for Large-Scale Linear Programming

Abstract: This master’s thesis concerns the implementation of a GPUaccelerated version of Mehrotra’s predictor-corrector interior point algorithm for large-scale linear programming (LP). The implementations are tested on LP problems arising in the financial industry, where there is high demand for faster LP solvers. The algorithm was implemented in C++, MATLAB and CUDA, using double precision for numerical stability. A performance comparison showed that the algorithm can be accelerated from 2x to 6x using an Nvidia GTX Titan Black GPU compared to using only an Intel Xeon E5-2630v2 CPU. The amount of memory on the GPU restricts the size of problems that can be solved, but all tested problems that are small enough to fit on the GPU could be accelerated.