Parallel Implementation of Lemke's Algorithm on the Hypercube

descriptionPublicationkeyboard_double_arrow_right Article 01 Feb 1991 Italy English Publisher:Institute for Operations Research and the Management Sciences (INFORMS)Journal:ORSA Journal on Computing, volume 3, pages 56-62 (issn: 0899-1499, eissn: 2326-3245,

Copyright policy )

Authors: Renato De Leone; Terence T.-H. Ow;

doi: 10.1287/ijoc.3.1.56

handle: 11581/241412

Parallel Implementation of Lemke's Algorithm on the Hypercube

- Summary
- Subjects
- Metrics

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.

Country

Italy

Related Organizations

University of Wisconsin–Oshkosh
United States
University of Camerino
Italy

Keywords

Mathematical Techniques; Hypercubes, Lemke's algorithm; Computer Programming, Computational methods for problems pertaining to operations research and mathematical programming, Lemke's algorithm, Parallel numerical computation, parallel implementations, Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming), linear complementarity

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average