Mathematics Colloquia and Seminars

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.