Abstract

Fourier-Motzkin elimination is a computationally expensive but powerful method to solve a system of linear inequalities. These systems arise e.g. in execution order analysis for loop nests or in integer linear programming. This paper focuses on the analysis, design and implementation of a parallel solver for distributed memory for large systems of linear inequalities using the Fourier-Motzkin elimination algorithm. We also measure the speedup of parallel solver and prove that this implementation results in good scalability.

Keywords

MSC

15A39, 65Y05, 68W15

Cite this article

@article{cai-2382,
  author  = {Ivan Šimeček and Richard Fritsch and Daniel Langr and Robert Lorencz},
  title   = {Parallel Solver of Large Systems of Linear Inequalities Using Fourier-Motzkin Elimination},
  journal = {Computing and Informatics},
  volume  = {35},
  number  = {6},
  pages   = {1307--1337},
  year    = {2016},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2016/6/parallel-solver-of-large-systems-of-linear-inequalities-using-fourier-motzkin-elimination/}
}
Download .bib