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

This master’s thesis concerns the implementation of a GPU-accelerated 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 C, using double precision for numerical stability.
A performance comparison showed that the algorithm could be accelerated 2x to 6x using an Nvidia GTX Titan Black compared to using only an Intel Xeon E5-2630v2. The amount of memory on the GPU restricts the size of problems that can be solved, but all tested problems small enough to fit on the GPU could be accelerated.