Conjugate gradient method for the linear complementarity problem with S-matrix

In this paper, we present a conjugate gradient method for solving the linear complementarity problem that involves an S-matrix. At each step, we solve a lower-dimensional system of linear equations by conjugate gradient method. The method terminates at the exact solution of the problem after a finite number of iterations. Moreover, the computational complexity of the proposed method is no more than the computational complexity of a conjugate gradient method for solving a system of linear equations. Preliminary numerical experiments show that the method is efficient.