Parallel Solver of Large Systems of Linear Inequalities Using Fourier-Motzkin Elimination

Authors

  • Ivan Šimeček Department of Computer Systems, FIT CTU in Prague
  • Richard Fritsch Department of Computer Systems, FIT CTU in Prague
  • Daniel Langr Department of Computer Systems, FIT CTU in Prague
  • Róbert Lórencz Department of Computer Systems, FIT CTU in Prague

Keywords:

Solver, linear inequalities, Fourier-Motzkin elimination, distributed algorithms, MPI, C

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.

Downloads

Download data is not yet available.

Downloads

Published

2017-02-10

How to Cite

Šimeček, I., Fritsch, R., Langr, D., & Lórencz, R. (2017). Parallel Solver of Large Systems of Linear Inequalities Using Fourier-Motzkin Elimination. COMPUTING AND INFORMATICS, 35(6), 1307–1337. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/2382

Issue

Vol. 35 No. 6 (2016): Computing and Informatics

Section

Articles