Parallel Implementation of Lemke's Algorithm on the Hypercube
Renato De Leone, Terence T.-H. Ow
ORSA Journal on Computing · 1991 · Volume 3 · Issue 1
Abstract
A simple but very effective method for parallelizing Lemke's algorithm for the solution of linear complementarity problems is presented. Implementation details on a 32-node Intel iPSC/2 hypercube for problems of dimension up to 1000 are discussed. A speedup efficiency as high as 76% is achieved with 32 processing nodes for a problem with 500 variables and 250,000 nonzero elements. By combining the effects of concurrency and vectorization the computing time on the Intel iPSC/2 in some cases is reduced by a factor of 100. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
programming: complementarity, linear, algorithms, linear complementarity, parallel algorithms, Lemke's algorithm, hypercube
Enable JavaScript for citation tools and additional paper interactions.