Implementing an Interior Point Method for Linear Programs on a CPU-GPU System
Department of Computer Science, University of Maryland, College Park, MD 20742, USA
Electronic Transactions on Numerical Analysis, Vol. 28 (2008), pp. 174-189.
@article{jung2008implementing,
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},
volume={28},
pages={174–189},
year={2008}
}
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.
October 27, 2010 by hgpu
