Solving Large-Scale Linear Programming Problems on Hypercube Computer

Heejae YANG  Myunghwan KIM  

IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.10   pp.1722-1724
Publication Date: 1990/10/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Algorithm, Data Structure and Computational Complexity

Full Text: PDF>>
Buy this Article

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.