Implementing an Interior Point Method for Linear Programs on a CPU-GPU System

Jin H. Jung, Dianne P. OLeary
Department of Computer Science, University of Maryland, College Park, MD 20742, USA
Electronic Transactions on Numerical Analysis, Vol. 28 (2008), pp. 174-189.


   title={Implementing an interior point method for linear programs on a CPU-GPU system},

   author={Jung, J.H. and OLEARY, D.P.},

   journal={Electronic Transactions on Numerical Analysis},





Download Download (PDF)   View View   Source Source   



Graphics processing units (GPUs), present in every laptop and desktop computer, are potentially powerful computational engines for solving numerical problems. We present a CPU-GPU algorithm for solving linear programming problems using interior point methods. This algorithm, based on the rectangular-packed matrix storage scheme of Gunnels and Gustavson, uses the GPU for computationally intensive tasks such as matrix assembly, Cholesky factorization, and forward and back substitution. Comparisons with a CPU implementation demonstrate that we can improve performance by using the GPU for sufficiently large problems. Since GPU architectures and programming languages are rapidly evolving, we expect that GPUs will be an increasingly attractive tool for matrix computation in the future.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: