Asynchronous parallel successive overrelaxation for the symmetric linear complementarity problem (Q1116899)

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.