Algorithms for weighted counting over parametric polytopes: A survey and a practical comparison

The polytope model is widely used in compiler analysis for representing a certain class of programs. Many counting problems that occur in the analysis of such programs can be solved by counting the number of integer points in a parametric polytope. In other counting problems, polynomial weights are assigned to the integer points of a parametric polytope and the objective is to find the sum of these weights over all integer points. This paper briefly surveys a number of algorithms for solving such problems. The paper also serves to document some of the algorithms implemented in the freely available barvinok library.status: publishe