Asynchronous parallel successive overrelaxation for the symmetric linear complementarity problem

Convergence is established for asynchronous parallel successive overrelaxation (SOR) algorithms for the symmetric linear complementarity problem. For the case of a strictly diagonally dominant matrix convergence is achieved for a relaxation factor interval of (0,2] with line search, and (0,1] without line search. Computational tests on the Sequent Symmetry S81 multiprocessor give speedup efficiency in the 43%-91% range for the cases for which convergence is established. The tests also show superiority of the asynchronous SOR algorithms over their synchronous counterparts.