Faster Integer Points Counting in Parametric Polyhedra

In this paper, we consider the counting function $E_P(y) = |P_{y} \cap Z^{n_x}|$ for a parametric polyhedron $P_{y} = \{x \in R^{n_x} \colon A x \leq b + B y\}$, where $y \in R^{n_y}$. We give a new representation of $E_P(y)$, called a \emph{piece-wise step-polynomial with periodic coefficients}, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart's quasi-polynomials. In terms of the computational complexity, our result gives the fastest way to calculate $E_P(y)$ in certain scenarios. The most remarkable cases are the following: 1) Consider a parametric polyhedron $P_y$ defined by a standard-form system $A x = y,\, x \geq 0$ with a fixed number of equalities. We show that there exists an $poly\bigl(n, \|A\|_{\infty}\bigr)$ preprocessing-algorithm that returns a polynomial-time computable representation of $E_P(y)$. That is, $E_(y)$ can be computed by a polynomial-time algorithm for any given $y \in Q^k$; 2) Again, assuming that the co-dimension 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 $E_P(y)$ is more efficient than other known approaches, if the matrix $A$ has bounded elements, especially if the matrix $A$ 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.