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

In: Computing and Informatics, vol. 35, no. 6

I. Šimeček - R. Fritsch - D. Langr - R. Lórencz

Details:

Year, pages: 2016, 1307 - 1337

Keywords:

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

About article:

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.

How to cite:

ISO 690:

Šimeček, I., Fritsch, R., Langr, D., Lórencz, R. 2016. Parallel Solver of Large Systems of Linear Inequalities Using Fourier-Motzkin Elimination. In Computing and Informatics, vol. 35, no.6, pp. 1307-1337. 1335-9150.

APA:

Šimeček, I., Fritsch, R., Langr, D., Lórencz, R. (2016). Parallel Solver of Large Systems of Linear Inequalities Using Fourier-Motzkin Elimination. Computing and Informatics, 35(6), 1307-1337. 1335-9150.