Return to Colloquia & Seminar listing
Convex hull computation in Normaliz
Special Events| Speaker: | Winfried Bruns, Universität Osnabrück |
| Location: | 1147 MSB |
| Start time: | Mon, Nov 28 2016, 12:10PM |
Normaliz is a versatile package for computations in discrete convex geometry: it computes lattice points in polyhedra, or, from a different perspective, solves linear diophantine systems of inequalities, equations and congruences.
Recently it has been included in benchmarks of convex hull computation (or vertex enumeration), and has often outperformed dedicated systems, especially on large problems. We will present Normaliz' approach to convex hulls. The main tool is pyramid decomposition whose development was sparked off by the more difficult task of computing triangulations. Pyramid decomposition allows "localization" and helps to break the often forbidding complexity of pure Fourier-Motzkin elimination. Furthermore it is parallelization friendly.
Based on: W. Bruns, B. Ichim and C. Söger, The power of pyramid decomposition in Normaliz, J. Symb. Comp. 74 (2016), 513-536.