Back to Search
Start Over
Analytical computation of Ehrhart polynomials
- Source :
- CASES
- Publication Year :
- 2004
- Publisher :
- ACM, 2004.
-
Abstract
- Many optimization techniques, including several targeted specifically at embedded systems, depend on the ability to calculate the number of elements that satisfy certain conditions. If these conditions can be represented by linear constraints, then such problems are equivalent to counting the number of integer points in (possibly) parametric polytopes. It is well known that this parametric count can be represented by a set of Ehrhart polynomials. Previously, interpolation was used to obtain these polynomials, but this technique has several disadvantages. Its worst-case computation time for a single Ehrhart polynomial is exponential in the input size, even for fixed dimensions. The worst-case size of such an Ehrhart polynomial (measured in bits needed to represent the polynomial) is also exponential in the input size. Under certain conditions this technique even fails to produce a solution. Our main contribution is a novel method for calculating Ehrhart polynomials {\em analytically}. It extends an existing method, based on Barvinok's decomposition, for counting the number of integer points in a non-parametric polytope. Our technique always produces a solution and computes polynomially-sized Ehrhart polynomials in polynomial time (for fixed dimensions). ispartof: pages:248-258 ispartof: Proceedings of the 2004 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES 2004) pages:248-258 ispartof: International Conference on Compilers, Architectures, and Synthesis for Embedded Systems (CASES 2004) location:Washington D.C. date:22 Sep - 25 Sep 2004 status: published
- Subjects :
- Barvinok's decomposition
Discrete mathematics
Mathematical optimization
Polynomial
Mathematics::Combinatorics
signed unimodular decomposition
compiler analysis
Computer science
parametric polytope
Polytope
Quasi-polynomial
polyhedral model
quasi-polynomial
Ehrhart polynomial
Mathematics::Metric Geometry
Polytope model
Time complexity
Interpolation
Integer (computer science)
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems
- Accession number :
- edsair.doi.dedup.....2ec0e8f409ce05757beb64d3d25c66c2