Numerical solution to linear complementarity problems and the evaluation of American options

In the Black-Scholes framework, the American option pricing problem can be discretized into a finite-dimensional linear complementarity problem. We compare the numerical performances of three algorithms for the linear complementarity problem: the pivotal algorithms of Lemke and of Borici and Luthi, and the iterative approach "Projected Successive Over-Relaxation". We conclude that a special-purpose algorithm can provide performances vastly superior to those of generic algorithms.