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.
Publié le : 2017-02-13
Classification:
Parallel and Distributed Computing,
Solver, linear inequalities, Fourier-Motzkin elimination, distributed algorithms, MPI, C++,
15A39, 65Y05, 68W15
@article{cai2382,
author = {Ivan \v Sime\v cek; Department of Computer Systems, FIT CTU in Prague and Richard Fritsch; Department of Computer Systems, FIT CTU in Prague and Daniel Langr; Department of Computer Systems, FIT CTU in Prague and R\'obert L\'orencz; Department of Computer Systems, FIT CTU in Prague},
title = {Parallel Solver of Large Systems of Linear Inequalities Using Fourier-Motzkin Elimination},
journal = {Computing and Informatics},
volume = {35},
number = {4},
year = {2017},
language = {en},
url = {http://dml.mathdoc.fr/item/cai2382}
}
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. Parallel Solver of Large Systems of Linear Inequalities Using Fourier-Motzkin Elimination. Computing and Informatics, Tome 35 (2017) no. 4, . http://gdmltest.u-ga.fr/item/cai2382/