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

keywords: Solver, linear inequalities, Fourier-Motzkin elimination, distributed algorithms, MPI, C++
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.
mathematics subject classification 2000: 15A39, 65Y05, 68W15
reference: Vol. 35, 2016, No. 6, pp. 1307–1337