Premium
A task‐based approach to parallel parametric linear programming solving, and application to polyhedral computations
Author(s) -
Coti Camille,
Monniaux David,
Yu Hang
Publication year - 2020
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.6050
Subject(s) - speedup , computer science , computation , parallel computing , redundancy (engineering) , parametric statistics , linear programming , task (project management) , parallel programming model , algorithm , programming paradigm , mathematics , programming language , statistics , management , economics , operating system
Summary 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.