For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Solving Large-Scale Linear Programming Problems on Hypercube Computer
Heejae YANG Myunghwan KIM
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/10/25
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Algorithm, Data Structure and Computational Complexity
Full Text: PDF>>
The use of hypercube multiprocessor computer for solving large-scale linear programming problems with parallel simplex method is presented. The inherent parallelisms involved in each step of the sequential simplex method are investigated and we show how the topological properties of hypercube are effectively applied in the proposed algorithm. The analysis shows that an O(P) speedup with respect to the total running time required by sequential implementations of the simplex method is achieved by using P2p processors of p-dimensional hypercube.