#
GPU Acceleration of the Matrix-Free Interior Point Method

###
Technical Report ERGO-11-008

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

**
Abstract
**

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

**
Text:
**

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.