Counting with rational generating functions

Title:
Counting with rational generating functions
Authors:
Verdoolaege, Sven; Woods, Kevin
Abstract:
We examine two different ways of encoding a counting function: as a rational generating function and explicitly as a function (defined piecewise using the greatest integer function). We prove that, if the degree and number of input variables of the (quasi-polynomial) function are fixed, there is a polynomial time algorithm which converts between the two representations. Examples of such counting functions include Ehrhart quasi-polynomials, vector partition functions, integer points in parametric polytopes, and projections of the integer points in parametric polytopes. For this last example, this algorithm provides the first known way to compute the explicit function in polynomial time. We rely heavily on results by Barvinok and Pommersheim [Barvinok, A., Pommersheim, J., 1999. An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–97). In: Math. Sci. Res. Inst. Publ., vol. 38. Cambridge Univ. Press, Cambridge, pp. 91–147], and also by Verdoolaege et al. [Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V., Bruynooghe, M., 2007. Counting integer points in parametric polytopes using Barvinok’s rational functions, Algorithmica 48 (1), 37–66].
Citation:
Verdoolaege, Sven, and Kevin Woods. 2008. "Counting with rational generating functions." Journal Of Symbolic Computation 43(2): 75-91.
Publisher:
Elsevier for Academic Press
DATE ISSUED:
2008-02
Department:
Mathematics
Type:
article
PUBLISHED VERSION:
10.1016/j.jsc.2007.07.007
PERMANENT LINK:
http://hdl.handle.net/11282/309166

Full metadata record

DC FieldValue Language
dc.contributor.authorVerdoolaege, Svenen_US
dc.contributor.authorWoods, Kevinen_US
dc.date.accessioned2013-12-23T16:03:52Zen
dc.date.available2013-12-23T16:03:52Zen
dc.date.issued2008-02en
dc.identifier.citationVerdoolaege, Sven, and Kevin Woods. 2008. "Counting with rational generating functions." Journal Of Symbolic Computation 43(2): 75-91.en_US
dc.identifier.issn0747-7171en_US
dc.identifier.urihttp://hdl.handle.net/11282/309166en
dc.description.abstractWe examine two different ways of encoding a counting function: as a rational generating function and explicitly as a function (defined piecewise using the greatest integer function). We prove that, if the degree and number of input variables of the (quasi-polynomial) function are fixed, there is a polynomial time algorithm which converts between the two representations. Examples of such counting functions include Ehrhart quasi-polynomials, vector partition functions, integer points in parametric polytopes, and projections of the integer points in parametric polytopes. For this last example, this algorithm provides the first known way to compute the explicit function in polynomial time. We rely heavily on results by Barvinok and Pommersheim [Barvinok, A., Pommersheim, J., 1999. An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–97). In: Math. Sci. Res. Inst. Publ., vol. 38. Cambridge Univ. Press, Cambridge, pp. 91–147], and also by Verdoolaege et al. [Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V., Bruynooghe, M., 2007. Counting integer points in parametric polytopes using Barvinok’s rational functions, Algorithmica 48 (1), 37–66].en_US
dc.publisherElsevier for Academic Pressen_US
dc.identifier.doi10.1016/j.jsc.2007.07.007en_US
dc.subject.departmentMathematicsen_US
dc.titleCounting with rational generating functionsen_US
dc.typearticleen_US
dc.identifier.journalJournal Of Symbolic Computationen_US
dc.subject.keywordRational generating functionen_US
dc.subject.keywordPiecewise quasi-polynomialsen_US
dc.subject.keywordVector partition functionsen_US
dc.subject.keywordParametric counting functionsen_US
dc.subject.keywordParametric polytopesen_US
dc.subject.keywordBarvinok algorithmen_US
dc.identifier.volume43en_US
dc.identifier.issue2en_US
dc.identifier.startpage75en_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.