GPU Acceleration of the Matrix-Free Interior Point Method

Technical Report ERGO-11-008

E. Smith, J. Gondzio, J.A.J. Hall


The matrix-free technique is an iterative approach to interior point methods (IPM), so named because both the solution procedure and the computation of an appropriate preconditioner require only the results of the operations Ax and A T y, where A is the matrix of constraint coefficients. This paper demonstrates its overwhelmingly superior performance on two classes of linear programming (LP) problems relative to both the simplex method and to IPM with equations solved directly. It is shown that the reliance of this technique on sparse matrix-vector operations enables further, significant performance gains from the use of a GPU, and from multi-core processors.

Key words: Matrix-Free, Interior Point Methods, GPU

Published in: R. Wyrzykowski, J. Dongarra, K. Karczewski and J. Wasniewski (eds.),
Parallel Processing and Applied Mathematics PPAM 2011, Part I,
Lecture Notes in Computer Science, 7203, Springer-Verlag, Berlin, 2012, pp 681-689.

Related Software:
HOPDM Higher Order Primal Dual Method.