A task‐based approach to parallel parametric linear programming solving, and application to polyhedral computations. (8th October 2020)

• Record Type: Journal Article
• Authors: Coti, Camille; Monniaux, David; Yu, Hang
• Is Part Of: Concurrency and computation. Volume 33:Number 6(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-10-08
• Subjects: parallel parametric linear programming -- polyhedra; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.6050
• Languages: English
• ISSNs: 1532-0626

Abstract

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.