Seminar Room, ground floor (Building IMAG)
19 December 2019 - 10h00
Towards an Efficient Parallel Parametric Linear Programming Solver (Phd Defense)
by Hang Yu from VERIMAG
Abstract: VPL (Verified Polyhedra Library) is an abstract polyhedra domain using constraint-only description. Allmain operators boiled down to polyhedral projection, which can be computed using Fourier-Motzkinelimination [20]. This method generates many redundant constraints which must be eliminated at ahigh cost. A novel algorithm was implemented in VPL for computing the polyhedral projection usingparametric linear programming(PLP) [36], which can replace Fourier-Motzkin elimination. This PLPsolver can also be used for computing the join operator (convex hull). Our work focuses on improvingthe efficiency of the algorithm of PLP solver.In prior work, PLP [34,1] was done in arbitrary precision rational arithmetic. In this work, wepresent an approach where most of the computations are performed in floating-point arithmetic, and thenexact rational results are reconstructed. The result obtained from our approach is guaranteed to be sound.We also propose a workaround for a difficulty calleddegeneracy, which plagued previous attempts atusing PLP for computations on polyhedra: in general the (parametric) linear programming problemsare degenerated, resulting in redundant computations and duplicates in geometric descriptions. Thealgorithm of the PLP solver is intrinsically parallelable, however it was developed in VPL with OCaml,which does not well support parallelism programming. In our approach, which is implemented withC++, we proposed a task-based scheme for parallelizing it. Two parallel implementations have beenrealized using two different parallel mechanisms: Intel’s Thread Building Blocks (TBB)1and OpenMPtasks [4].
Jury composé de :
- Christophe Alias, chargé de recherche à INRIA Lyon, rapporteur
- Philippe Clauss, professeur à l'Université de Strasbourg, rapporteur
- Nadia Brauner, professeur à l'Université Grenoble Alpes, examinatrice
- Liqian Chen, maître de conférences à l'Université nationale de technologie de défense à Changsha (Chine), examinateur
- David Monniaux, directeur de recherche au CNRS, directeur de thèse
- Michaël Périn, maître de conférences à l'Université Grenoble Alpes, co-encadrant
