Title: Algorithms for weighted counting over parametric polytopes: A survey and a practical comparison
Authors: Verdoolaege, Sven ×
Bruynooghe, Maurice #
Issue Date: Jul-2008
Host Document: The 2008 International Conference on Information Theory and Statistical Learning pages:60-66
Conference: Information-Theoretic Aspects of Integer-Point Enumeration in Polyhedra edition:1 location:Las Vegas date:July 2008
Abstract: 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, extending them where needed and
evaluating them on a set of realistic and constructed
examples from compiler analysis and beyond.
The paper also serves to document some of the algorithms
implemented in the freely available
barvinok library.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
ITS6311.pdfMain article Published 115KbAdobe PDFView/Open
handouts4.pspresentation Published 358KbPostscriptView/Open
slides.pdfpresentation Published 508KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.