Volume 28, pp. 174-189, 2007-2008.

Implementing an interior point method for linear programs on a CPU-GPU system

Jin Hyuk Jung and Dianne P. O'Leary

Abstract

Graphics processing units (GPUs), present in every laptop and desktop computer, are potentially powerful computational engines for solving numerical problems. We present a mixed precision 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.

Full Text (PDF) [711 KB]

Key words

GPGPU, Cholesky factorization, matrix decomposition, forward and back substitution, linear programming, interior point method, rectangular packed format

AMS subject classifications

90C05, 90C51, 15A23, 68W10

< Back