An algorithm for the fast solution of symmetric linear complementarity problems

José Luis Morales, Jorge Nocedal*, Mikhail Smelyanskiy

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe (Numer Math 68:95-106, 1994) that combines projected Gauss-Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimization designed to handle severely ill-conditioned problems. Numerical tests indicate that the approach is more efficient than interior-point and gradient projection methods on some physical simulation problems that arise in computer game scenarios.

Original languageEnglish (US)
Pages (from-to)251-266
Number of pages16
JournalNumerische Mathematik
Issue number2
StatePublished - Dec 2008

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'An algorithm for the fast solution of symmetric linear complementarity problems'. Together they form a unique fingerprint.

Cite this