Solving Large-Scale Linear Programming Problems on Hypercube Computer

Heejae YANG; Myunghwan KIM

Solving Large-Scale Linear Programming Problems on Hypercube Computer

Heejae YANG, Myunghwan KIM

Full Text Views

0

Share
Cite this

Summary :

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 P2^p processors of p-dimensional hypercube.

Publication: IEICE TRANSACTIONS on transactions Vol.E73-E No.10 pp.1722-1724

Publication Date: 1990/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: LETTER

Category: Algorithm, Data Structure and Computational Complexity

Authors

Heejae YANG
Myunghwan KIM

Keyword

Cite this

Copy

Heejae YANG, Myunghwan KIM, "Solving Large-Scale Linear Programming Problems on Hypercube Computer" in IEICE TRANSACTIONS on transactions, vol. E73-E, no. 10, pp. 1722-1724, October 1990, doi: .
Abstract: 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 P2^p processors of p-dimensional hypercube.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e73-e_10_1722/_p

Copy

@ARTICLE{e73-e_10_1722,
author={Heejae YANG, Myunghwan KIM, },
journal={IEICE TRANSACTIONS on transactions},
title={Solving Large-Scale Linear Programming Problems on Hypercube Computer},
year={1990},
volume={E73-E},
number={10},
pages={1722-1724},
abstract={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 P2^p processors of p-dimensional hypercube.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Solving Large-Scale Linear Programming Problems on Hypercube Computer
T2 - IEICE TRANSACTIONS on transactions
SP - 1722
EP - 1724
AU - Heejae YANG
AU - Myunghwan KIM
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 10
JA - IEICE TRANSACTIONS on transactions
Y1 - October 1990
AB - 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 P2^p processors of p-dimensional hypercube.
ER -