Parallel pivotal algorithm for solving the linear complementarity problem |
| |
Authors: | K T Medhi |
| |
Institution: | (1) AT&T, Kansas City, Missouri |
| |
Abstract: | We propose a parallel implementation of the classical Lemke's algorithm for solving the linear complementarity problem. The algorithm is designed for a loosely coupled network of computers which is characterized by relatively high communication costs. We provide an accurate prediction of speedup based on a simple operation count. The algorithm produces speedup nearp, wherep is the number of processors, when tested on large problems as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-84-20963 and DCR-850-21228 and by Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the University of Wisconsin, Madison, Wisconsin. |
| |
Keywords: | Parallel algorithms Lemke's algorithm linear complementarity problem distributed algorithms |
本文献已被 SpringerLink 等数据库收录! |
|