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