Data mapping of linear programming on fixed-size hypercubes

Gen Huey Chen, Hong Fa Ho, Shieu Hong Lin, Jang Ping Sheu

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Although many solution methods are available for the linear programming problem, the simplex method is undoubtedly the most widely used one for its simplicity. In this paper, we propose an implementation of the simplex method on fixed-size hypercubes. A partitioning technique and a mapping technique are presented to fit large-size problem instances into relatively small-size hypercubes. Two cases, pipelined broadcasting allowed and pipelined broadcasting not allowed, are considered. We show that the proposed implementation achieves the linear speedup asymptotically for both cases. Also, under the given mapping method, we discuss how to partition data so as to minimize the total run time and the communication time. We derive sufficient conditions for optimal partitionings. These sufficient conditions are helpful to obtain better partitionings. The optimal partitioning is obtained for a special case.

Original languageEnglish
Pages (from-to)235-243
Number of pages9
JournalParallel Computing
Volume13
Issue number2
DOIs
Publication statusPublished - 1990 Feb

Keywords

  • Linear programming
  • data mapping
  • hypercubes
  • simplex method

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Data mapping of linear programming on fixed-size hypercubes'. Together they form a unique fingerprint.

  • Cite this