Advanced search
2 files | 560.67 KB

Experiences with enumeration of integer projections of parametric polytopes

Author
Organization
Abstract
Many compiler optimization techniques depend on the ability to calculate the number of integer values that satisfy a given set of linear constraints. This count (the enumerator of a parametric polytope) is a function of the symbolic parameters that may appear in the constraints. In an extended problem (the "integer projection" of a parametric polytope), some of the variables that appear in the constraints may be existentially quantified and then the enumerated set corresponds to the projection of the integer points in a parametric polytope. This paper shows how to reduce the enumeration of the integer projection of parametric polytopes to the enumeration of parametric polytopes. Two approaches are described and experimentally compared. Both can solve problems that were considered very difficult to solve analytically.
Keywords
EQUATIONS

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 309.60 KB
  • Verdoolaege 2005 ICCC14 91.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 251.06 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Verdoolaege, Sven, Kristof Beyls, Maurice Bruynooghe, and Francky Catthoor. 2005. “Experiences with Enumeration of Integer Projections of Parametric Polytopes.” Ed. Rastislav Bodik. Lecture Notes in Computer Science 3443: 91–105.
APA
Verdoolaege, S., Beyls, K., Bruynooghe, M., & Catthoor, F. (2005). Experiences with enumeration of integer projections of parametric polytopes. (R. Bodik, Ed.)LECTURE NOTES IN COMPUTER SCIENCE, 3443, 91–105. Presented at the 14th International Conference on Compiler Construction.
Vancouver
1.
Verdoolaege S, Beyls K, Bruynooghe M, Catthoor F. Experiences with enumeration of integer projections of parametric polytopes. Bodik R, editor. LECTURE NOTES IN COMPUTER SCIENCE. Berlin, Germany: Springer; 2005;3443:91–105.
MLA
Verdoolaege, Sven et al. “Experiences with Enumeration of Integer Projections of Parametric Polytopes.” Ed. Rastislav Bodik. LECTURE NOTES IN COMPUTER SCIENCE 3443 (2005): 91–105. Print.
@article{334427,
  abstract     = {Many compiler optimization techniques depend on the ability to calculate the number of integer values that satisfy a given set of linear constraints. This count (the enumerator of a parametric polytope) is a function of the symbolic parameters that may appear in the constraints. In an extended problem (the "integer projection" of a parametric polytope), some of the variables that appear in the constraints may be existentially quantified and then the enumerated set corresponds to the projection of the integer points in a parametric polytope.
This paper shows how to reduce the enumeration of the integer projection of parametric polytopes to the enumeration of parametric polytopes. Two approaches are described and experimentally compared. Both can solve problems that were considered very difficult to solve analytically.},
  author       = {Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Catthoor, Francky},
  editor       = {Bodik, Rastislav},
  isbn         = {9783540254119},
  issn         = {0302-9743},
  journal      = {LECTURE NOTES IN COMPUTER SCIENCE},
  keywords     = {EQUATIONS},
  language     = {eng},
  location     = {Edinburgh, Scotland, UK},
  pages        = {91--105},
  publisher    = {Springer},
  title        = {Experiences with enumeration of integer projections of parametric polytopes},
  url          = {http://dx.doi.org/10.1007/b107108},
  volume       = {3443},
  year         = {2005},
}

Altmetric
View in Altmetric
Web of Science
Times cited: