Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration

In this paper, we address the problem of counting integer points in a rational polytope described by $P(y) = { x \in $\mathbb{R}$^m \colon Ax = y, x \geq 0}$,where$A$isan$n \times m$integermatrixand$y$isan$n$-dimensional integer vector. We study the Z-transformation approach initiated by Brion-Vergne, Beck, and Lasserre-Zeron from the numerical analysis point of view, and obtain a new algorithm on this problem: If $A$ is nonnegative, then the number of integer points in $P(y)$ can be computed in $O(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n,m,\mathrm{\parallel }y{\mathrm{\parallel }}_{\mathrm{\infty }})(\mathrm{\parallel }y{\mathrm{\parallel }}_{\mathrm{\infty }}+1{)}^n)$ time and $O(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n,m,\mathrm{\parallel }y{\mathrm{\parallel }}_{\mathrm{\infty }}))$ space.This improves, in terms of space complexity, a naive DP algorithm with $O((\mathrm{\parallel }y{\mathrm{\parallel }}_{\mathrm{\infty }}+1{)}^n)$-size DP table. Our result is based on the standard error analysis to the numerical contour integration for the inverse Z-transform, and establish a new type of an inclusion-exclusion formula for integer points in $P(y)$. We apply our result to hypergraph $b$-matching, and obtain a $O($\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$( n,m,|b|\infty) (|b|\infty +1)^{(1-1/k)n})$timealgorithmforcounting$b$-matchingsina$k$-partitehypergraphwith$n$verticesand$m$ hyperedges. This result is viewed as a $b$-matching generalization of the classical result by Ryser for $k=2$ and its multipartite extension by Bj{"o}rklund-Husfeldt.