| Home > Publications > Reports > Informatics (CW) |
CW 376
Sven Verdoolaege, Kristof Beyls, Maurice Bruynooghe, Rachid Seghir, Vincent Loechner
Analytical Computation of Ehrhart Polynomials and its Applications for Embedded Systems
Abstract
Many optimization techniques, including several targeted specifically at embedded systems, depend on the ability to calculate the number of points in a parametrized polytope. It is well known that this parametrized count can be represented by an Ehrhart polynomial, which is usually computed through interpolation. In some cases, however, this interpolation fails and in some other cases it can take a very long time to compute. By extending an existing method, based on Barvinok's decomposition, to count the number of points in an non-parameterized polytope we show that we can compute the Ehrhart polynomial {\em analytically}, solving these problems to a large extent.
report.pdf (192K) / mailto: S. Verdoolaege