A task-based approach to parallel parametric linear programming solving, and application to polyhedral computations

摘要

Parametric linear programming is a central operation for polyhedral computations, as well as in certain control applications. Here, we propose a task-based scheme for parallelizing it, with quasi-linear speedup over large problems. This type of parallel applications is challenging, because several tasks might be computing the same region. In this article, we are presenting the algorithm itself with a parallel redundancy elimination algorithm, and conducting a thorough performance analysis.