A new and faster representation for counting integer points in parametric polyhedra

Abstract

In this paper, we consider the counting function EP (y) = | Py ∩ Z nx | for a parametric polyhedron Py = {x ∈ R nx : Ax ≤ b + By}, where y ∈ R ny . We give a new representation of EP (y), called a piece-wise step-polynomial with periodic coefficients, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart’s quasi-polynomials. It gives the fastest way to calculate EP (y) in certain scenarios. The most important cases are the following: 1) We show that, for the parametric polyhedron Py defined by a standardform system Ax = y, x ≥ 0 with a fixed number of equalities, the function EP (y) can be represented by a polynomial-time computable function. In turn, such a representation of EP (y) can be constructed by an poly n, ∥A∥∞
-time algorithm 2) Assuming again that the number of equalities is fixed, we show that integer/rational Ehrhart’s quasi-polynomials of a polytope can be computed by FPT-algorithms, parameterized by sub-determinants of A or its elements; 3) Our representation of EP is more efficient than other known approaches, if A has bounded elements, especially if it is sparse in addition; Additionally, we provide a discussion about possible applications in the area of compiler optimization. In some “natural” assumptions on a program code, our approach has the fastest complexity bounds.