doc/barvinok.bib

   1 @string(ICPS = "ICPS, Universit\'e Louis Pasteur de Strasbourg, France")
   2 @string(Passau = {Universit\"at Passau})
   3
   4 @techreport{ Wilde1993,
   5     author = "D. K. Wilde",
   6     title = "A Library for doing polyhedral operations",
   7     number = "785",
   8     institution = "IRISA, Rennes, France",
   9     pages = "45 p.",
  10     year = 1993,
  11     url = "citeseer.nj.nec.com/article/wilde93library.html",
  12     note = "\\http://www.irisa.fr/EXTERNE/bibli/pi/pi785.html"
  13 }
  14
  15 @article{ Loechner97parameterized,
  16     author = "Vincent Loechner and Doran K. Wilde",
  17     title = "Parameterized Polyhedra and Their Vertices",
  18     journal = "International Journal of Parallel Programming",
  19     volume = "25",
  20     number = "6",
  21     pages = "525--549",
  22     year = "1997",
  23     month = dec,
  24     publisher = {Kluwer Academic Publishers},
  25     url = "citeseer.nj.nec.com/article/loechner95parameterized.html" }
  26
  27 @TechReport{ Loechner1999,
  28     author = "Vincent Loechner",
  29     month = mar,
  30     year = 1999,
  31     title = "PolyLib: A Library for Manipulating Parameterized Polyhedra",
  32     institution = ICPS,
  33 }
  34
  35 @article{ Clauss1998parametric,
  36     author = "Clauss, Philippe and Loechner, Vincent",
  37     title = "Parametric analysis of polyhedral iteration spaces",
  38     journal = "Journal of {VLSI} Signal Processing",
  39     publisher = "Kluwer Academic Publishers, Boston",
  40     year = "1998",
  41     volume = 19,
  42     pages = "179--194",
  43     number = 2,
  44     month = jul,
  45 }
  46
  47 @mastersthesis{ Seghir2002,
  48     title = {D\'enombrement des Point Entiers de l'Union et de
  49              l'Image des Poly\'edres Param\'etr\'es},
  50     author = "Rachid Seghir",
  51     month = jun,
  52     school = ICPS,
  53     year = 2002,
  54 }
  55
  56 @techreport{cdd,
  57     author = "K. Fukuda",
  58     title = "cdd.c: C-implementation of the double description method for computing all vertices and extremal rays of a convex polyhedron given by a system of linear inequalities",
  59     institution = "Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, Switzerland",
  60    year =  1993,
  61     note = "program available from http://www.ifor.math.ethz.ch/~fukuda/fukuda.html",
  62 }
  63
  64 @PhdThesis{Loechner97phd,
  65     author = "V. Loechner",
  66     title = {Contribution \`a l'\'etude des poly\`edres
  67 param\'etr\'es et applications en parall\'elisation automatique},
  68     school = "University Louis Pasteur, Strasbourg",
  69     year =  1997,
  70 }
  71
  72 @PHDTHESIS{ Bik1996PhD,
  73   AUTHOR    = {A. J. C. Bik},
  74   TITLE     = {Compiler Support for Sparse Matrix Computations},
  75   SCHOOL    = {University of Leiden},
  76   ADDRESS   = {The Netherlands},
  77   YEAR      = {1996},
  78   ISBN      = {},
  79   NOTE      = {},
  80   CONTENTS  = {},
  81   sourceURL = {ftp://ftp.wi.leidenuniv.nl/pub/CS/PhDTheses/bik-96.ps.gz},
  82   FLAGS     = {own},
  83   TOPICS    = {Sparse Arrays}
  84 }
  85
  86 @PHDTHESIS{Verdoolaege2005PhD,
  87   AUTHOR = "Verdoolaege, Sven",
  88   TITLE = {Incremental Loop Transformations and Enumeration of Parametric Sets},
  89   SCHOOL = {Department of Computer Science, K.U.Leuven},
  90   YEAR = {2005},
  91   TYPE = {PHD},
  92   ADDRESS = {Leuven, Belgium},
  93   MONTH = apr,
  94 }
  95
  96 @misc{latte1.1,
  97     author = "De Loera, J. A. and Haws, D. and Hemmecke, R. and Huggins, P. and Tauzer, J. and Yoshida, R.",
  98     title = "A User's Guide for LattE v1.1",
  99     year = 2003,
 100     month = nov,
 101     note = {software package {\tt LattE} is available at {\tt http://www.math.ucdavis.edu/$\sim$latte/}},
 102 }
 103
 104 @misc{NTL,
 105     author = "Victor Shoup",
 106     title = "{NTL}",
 107     note = "Available from {\tt http://www.shoup.net/ntl/}",
 108     year = 2004,
 109 }
 110
 111 @incollection{polymake,
 112   author =       {Ewgenij Gawrilow and Michael Joswig},
 113   title =        {polymake: a Framework for Analyzing Convex Polytopes},
 114   pages =        {43-74},
 115   editor =       {Gil Kalai and G\"unter M. Ziegler},
 116   booktitle =    {Polytopes --- Combinatorics and Computation},
 117   publisher =    {Birkh\"auser},
 118   year =         {2000}
 119 }
 120
 121 @article{Stanley93monotonicity,
 122   author    = {Richard P. Stanley},
 123   title     = {A Monotonicity Property of h-vectors and h*-vectors.},
 124   journal   = {European Journal of Combinatorics},
 125   volume    = {14},
 126   number    = {3},
 127   year      = {1993},
 128   pages     = {251-258},
 129 }
 130
 131 @TechReport{ Omega_calc,
 132     author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott",
 133     title = "The {Omega} Calculator and Library",
 134     month = nov,
 135     institution = "University of Maryland",
 136     year = 1996
 137 }
 138
 139 @TechReport{ Omega_lib,
 140     author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott",
 141     title = "The {Omega} Library",
 142     month = nov,
 143     institution = "University of Maryland",
 144     year = 1996
 145 }
 146
 147 @inproceedings{Turjan2002,
 148     author = "Alexandru Turjan and Bart Kienhuis and Ed Deprettere",
 149     title = "A compile time based approach for solving out-of-order communication in {Kahn} Process Networks",
 150     booktitle = "IEEE 13th International Conference on Aplication-specific Systems, Architectures and Processors (ASAP'2002)",
 151     location = "San Jose, CA, USA",
 152     month = Jul,
 153     year =  2002
 154 }
 155
 156 @article{Loechner2002,
 157  author = {Vincent Loechner and Beno\^it Meister and Philippe Clauss},
 158  title = {Precise Data Locality Optimization of Nested Loops},
 159  journal = {J. Supercomput.},
 160  volume = {21},
 161  number = {1},
 162  year = {2002},
 163  issn = {0920-8542},
 164  pages = {37--76},
 165  doi = {http://dx.doi.org/10.1023/A:1013535431127},
 166  publisher = {Kluwer Academic Publishers},
 167  }
 168
 169 @inproceedings{Verdoolaege2004embedded,
 170   AUTHOR = "Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Seghir, Rachid and Loechner, Vincent",
 171   TITLE = {{A}nalytical computation of {E}hrhart polynomials and its applications for embedded systems},
 172   YEAR = {2004},
 173   booktitle = {2nd Workshop on Optimization for DSP and Embedded Systems, ODES-2},
 174   location = {Palo Alto, USA},
 175   month =  mar,
 176 }
 177
 178 @TECHREPORT{Verdoolaege2004TR,
 179   AUTHOR = "Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Seghir, Rachid and Loechner, Vincent",
 180   TITLE = {{A}nalytical computation of {E}hrhart polynomials and its applications for embedded systems},
 181   INSTITUTION = {Department of Computer Science, K.U.Leuven},
 182   YEAR = {2004},
 183   TYPE = {Report CW},
 184   NUMBER = {376},
 185   ADDRESS = {Leuven, Belgium},
 186   MONTH = {jan},
 187 NOTE = {URL = http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW376.abs.html},
 188 }
 189
 190 @TechReport{Seghir2004analytical,
 191         title = {Analytical Computation of {Ehrhart} Polynomials and its Application in Compile-Time Generated Cache Hints},
 192         author= {Rachid Seghir and Sven Verdoolaege and Kristof Beyls and Vincent Loechner},
 193         month = feb,
 194         year  = {2004},
 195         number = 118,
 196         institution = ICPS,
 197 }
 198
 199 @INPROCEEDINGS{Verdoolaege2004analytical,
 200   AUTHOR = "Verdoolaege, Sven and Seghir, Rachid and Beyls, Kristof and Loechner, Vincent and Bruynooghe, Maurice",
 201   TITLE = {{A}nalytical computation of {E}hrhart polynomials: {Enabling} more compiler analyses and optimizations},
 202   BOOKTITLE = {{P}roceedings of {I}nternational {C}onference on {C}ompilers, {A}rchitectures, and {S}ynthesis for {E}mbedded {S}ystems, {W}ashington {D}.{C}.},
 203   YEAR = {2004},
 204   pages = {248--258},
 205   month = sep,
 206 }
 207
 208 @TECHREPORT{Verdoolaege2004experiences,
 209   AUTHOR = "Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Catthoor, Francky",
 210   TITLE = {{E}xperiences with enumeration of integer projections of parametric polytopes},
 211   INSTITUTION = {K.U.Leuven, Department of Computer Science},
 212   YEAR = {2004},
 213   TYPE = {Report CW},
 214   NUMBER = {395},
 215   MONTH = oct,
 216 NOTE = {URL = http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW395.abs.html},
 217 }
 218
 219 @INPROCEEDINGS{Verdoolaege2005experiences,
 220   AUTHOR = "Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Catthoor, Francky",
 221   TITLE = {{E}xperiences with enumeration of integer projections of parametric polytopes},
 222   BOOKTITLE = {{P}roceedings of 14th {I}nternational {C}onference on {C}ompiler {C}onstruction, {E}dinburgh, {S}cotland},
 223   YEAR = {2005},
 224   EDITOR = {Bodik, R.},
 225   VOLUME = 3443,
 226     pages = "91-105",
 227     series = "Lecture Notes in Computer Science",
 228     publisher = "Springer-Verlag",
 229     address = "Berlin",
 230 }
 231
 232 @TECHREPORT{Verdoolaege2005barvinok,
 233   AUTHOR = "Verdoolaege, Sven and Woods, Kevin M. and Bruynooghe, Maurice and
 234 Cools, Ronald",
 235   YEAR = {2005},
 236   TITLE = {Computation and Manipulation of Enumerators of Integer Projections of
 237  Parametric Polytopes},
 238   TYPE = {Report CW},
 239   NUMBER = {392},
 240   INSTITUTION = {Dept.\ of Computer Science, K.U.Leuven},
 241   ADDRESS = {Leuven, Belgium},
 242 }
 243
 244 @article{Verdoolaege2008counting,
 245     author = {Sven Verdoolaege and Kevin M. Woods},
 246     title = {Counting with rational generating functions},
 247     journal = {J. Symb. Comput.},
 248     volume = {43},
 249     number = {2},
 250     year = {2008},
 251     issn = {0747-7171},
 252     pages = {75--91},
 253     doi = {http://dx.doi.org/10.1016/j.jsc.2007.07.007},
 254     publisher = {Academic Press, Inc.},
 255     address = {Duluth, MN, USA},
 256 }
 257
 258 @article{Verdoolaege2007parametric,
 259     author = "S. Verdoolaege and R. Seghir and K. Beyls and V. Loechner and M. Bruynooghe",
 260     title = "Counting integer points in parametric polytopes using {Barvinok}'s rational functions",
 261     journal = "Algorithmica",
 262     year = 2007,
 263     volume = 48,
 264     number = 1,
 265     month = jun,
 266     publisher = "Springer New York",
 267     pages = "37--66",
 268 }
 269
 270 @INPROCEEDINGS{Seghir2006memory,
 271   AUTHOR = "Rachid Seghir and Vincent Loechner",
 272   TITLE = {Memory Optimization by Counting Points in Integer Transformations of Parametric Polytopes},
 273   BOOKTITLE = {{P}roceedings of the {I}nternational {C}onference on {C}ompilers, {A}rchitectures, and {S}ynthesis for {E}mbedded Systems, CASES 2006, {S}eoul, {K}orea},
 274   month = oct,
 275   YEAR = {2006}
 276 }
 277
 278 @article{Koeppe2006primal,
 279     title = {{A primal Barvinok algorithm based on irrational decompositions}},
 280     author = {Matthias K\"oppe},
 281   year =         2007,
 282   journal =      {SIAM Journal on Discrete Mathematics},
 283   volume = 21,
 284   number = 1,
 285   pages = {220--236},
 286   doi = {10.1137/060664768},
 287 }
 288
 289 @article{Beck2009Brion,
 290   author = {Matthias Beck and Christian Haase and Frank Sottile},
 291   title = {Formulas of {Brion}, {Lawrence}, and {Varchenko} on rational generating  functions for cones},
 292   journal = "The Mathematical Intelligencer",
 293   publisher = "Springer New York",
 294   doi = "10.1007/s00283-008-9013-y",
 295   volume = 31,
 296   number = 1,
 297   month = jan,
 298   year = 2009,
 299 }
 300
 301 @article{Lasserre2005alternative,
 302     author = "Jean B. Lasserre and Eduardo S. Zeron",
 303     title = "An alternative algorithm for counting lattice points in a convex polytope",
 304     year = 2005,
 305     volume = 30,
 306     page = "597--614",
 307     journal = "Math. Oper. Res.",
 308 }
 309
 310 @article{Beyls2005hints,
 311 author= {Beyls, Kristof and  D'Hollander, Erik},
 312 title= {Generating Cache Hints for Improved Program Efficiency},
 313 journal= {Journal of Systems Architecture},
 314 year= {2005},
 315 month= {4},
 316 volume= {51},
 317 number= {4},
 318 pages= {223-250},
 319 publisher= {Elsevier},
 320 }
 321
 322 @TechReport{CFGV06,
 323   author       = {Clauss, P. and Fern\'andez, F. J. and Garbervetsky, D. and Verdoolaege, S.},
 324   title        = {Symbolic Polynomial Maximization over Convex Sets and its Application to Memory Requirement Estimation},
 325   institution  = {Universit\'e Louis Pasteur},
 326   number       = {06-04},
 327   month        = oct,
 328   year         = {2006},
 329   type         = {ICPS Research Report},
 330   url          = {http://icps.u-strasbg.fr/upload/icps-2006-173.pdf},
 331 }
 332
 333 @article{Cook1993implementation,
 334 AUTHOR={William Cook and Thomas Rutherford and Herbert E. Scarf and David F. Shallcross},
 335 TITLE={An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming},
 336 YEAR=1993,
 337 journal = "ORSA Journal on Computing",
 338 volume = 5,
 339 number = 2,
 340 }
 341
 342 @misc{GLPK,
 343 author = "Andrew Makhorin",
 344 title = "GNU Linear Programming Kit, Reference Manual, Version 4.11",
 345 year = 2006,
 346 month = jul,
 347 }
 348
 349 @inproceedings{Verdoolaege2006odes,
 350   AUTHOR = "Verdoolaege, Sven and Nikolov, Hristo and Stefanov, Todor",
 351   TITLE = {Improved Derivation of Process Networks},
 352   YEAR = {2006},
 353   booktitle = {4th Workshop on Optimization for DSP and Embedded Systems, ODES-4},
 354   location = {New York, USA},
 355   month =  mar,
 356 }
 357
 358 @article{Verdoolaege2007pn,
 359   AUTHOR = "Verdoolaege, Sven and Nikolov, Hristo and Stefanov, Todor",
 360   TITLE = {pn: A Tool for Improved Derivation of Process Networks},
 361   YEAR = {2007},
 362   volume = 2007,
 363   journal = "EURASIP Journal on Embedded Systems, special issue on
 364             Embedded Digital Signal Processing Systems",
 365   doi = {10.1155/2007/75947},
 366   publisher = "Hindawi Publishing Corporation",
 367 }
 368
 369 @article{Scarf2006Neighborhood,
 370   author    = {Herbert E. Scarf and
 371                Kevin M. Woods},
 372   title     = {Neighborhood Complexes and Generating Functions for Affine
 373                Semigroups.},
 374   journal   = {Discrete {\&} Computational Geometry},
 375   volume    = {35},
 376   number    = {3},
 377   year      = {2006},
 378   pages     = {385-403},
 379   ee        = {http://dx.doi.org/10.1007/s00454-005-1222-y},
 380   bibsource = {DBLP, http://dblp.uni-trier.de}
 381 }
 382
 383 @ARTICLE{Scarf1981indivisibilities:II,
 384 AUTHOR={Scarf, Herbert E},
 385 TITLE={Production Sets with Indivisibilities-Part {II}: The Case of Two Activities},
 386 JOURNAL={Econometrica},
 387 YEAR=1981,
 388 VOLUME={49},
 389 NUMBER={2},
 390 PAGES={395-423},
 391 MONTH=Mar,
 392 }
 393
 394 @phdthesis{Meister2004PhD,
 395     title = {Stating and Manipulating Periodicity in the Polytope Model. Applications to Program Analysis and Optimization},
 396     author= {Beno\^it Meister},
 397     institution = {Universit\'e Louis Pasteur},
 398     month = Dec,
 399     year  = {2004},
 400     school = ICPS,
 401 }
 402
 403 @article{Feautrier88parametric,
 404     author = "P. Feautrier",
 405     title = "Parametric Integer Programming",
 406     journal = "Operationnelle/Operations Research",
 407     volume = "22",
 408     number = "3",
 409     pages = "243--268",
 410     year = "1988",
 411     url = "citeseer.nj.nec.com/feautrier88parametric.html",
 412 }
 413
 414 @InProceedings{Gomory1963,
 415   author       = "R. E. Gomory",
 416   editor       = "R. L. Graves and P. Wolfe",
 417   booktitle    = "Recent Advances in Mathematical Programming",
 418   title        = "An algorithm for integer solutions to linear programming",
 419   publisher    = "McGraw-Hill",
 420   address      = "New York",
 421   pages        = "269--302",
 422   year         = "1963",
 423 }
 424
 425 @misc{Feautrier:PIP,
 426     author = "Paul Feautrier",
 427     title = "Solving Systems of Affine (In)Equalities: {PIP}'s User's Guide",
 428     year = 2006,
 429 }
 430
 431 @inproceedings{Barvinok1992volume,
 432  author = {Alexander I. Barvinok},
 433  title = {Computing the volume, counting integral points, and exponential sums},
 434  booktitle = {Proceedings of the eighth annual symposium on Computational geometry},
 435  year = {1992},
 436  isbn = {0-89791-517-8},
 437  pages = {161--170},
 438  location = {Berlin, Germany},
 439  doi = {http://doi.acm.org/10.1145/142675.142713},
 440  publisher = {ACM Press},
 441 }
 442
 443 @misc{Koeppe2006experiments,
 444     title = "Experiments with an algebraic scheme for estimating the number of lattice points in polyhedra",
 445     author = {De Loera, Jes\'us A. and Matthias K\"oppe},
 446     year = 2006,
 447     note = "Manuscript in preparation",
 448 }
 449
 450 @article{DeLoera2003effective,
 451     title = "Effective Lattice Point Counting in Rational Convex Polytopes",
 452     author = "De Loera, Jes\'us A. and Raymond Hemmecke and
 453               Jeremiah Tauzer and Ruriko Yoshida",
 454     year = 2004,
 455     journal = "The Journal of Symbolic Computation",
 456     volume = 38,
 457     number = 4,
 458     pages = "1273--1302",
 459     url = "http://www.math.ucdavis.edu/~latte/theory.html",
 460 }
 461
 462 @article{Barvinok1994,
 463     author = "A. I. Barvinok",
 464     title = "Computing the {Ehrhart} polynomial of a convex lattice polytope",
 465     journal = "Dicrete Comput. Geom.",
 466     volume =  12,
 467     year = 1994,
 468     pages = "35--48",
 469 }
 470
 471 @article {Brion88,
 472     AUTHOR = {Brion, Michel},
 473      TITLE = {Points entiers dans les poly\`edres convexes},
 474    JOURNAL = {Ann. Sci. \'Ecole Norm. Sup. (4)},
 475   FJOURNAL = {Annales Scientifiques de l'\'Ecole Normale Sup\'erieure.
 476               Quatri\`eme S\'erie},
 477     VOLUME = {21},
 478       YEAR = {1988},
 479     NUMBER = {4},
 480      PAGES = {653--663},
 481       ISSN = {0012-9593},
 482      CODEN = {ASENAH},
 483    MRCLASS = {52A43 (11H06 12L10 14F12 32C40)},
 484   MRNUMBER = {90d:52020},
 485 MRREVIEWER = {Daniel Barlet},
 486 }
 487
 488 @article{Koeppe2008parametric,
 489     title = {Computing parametric rational generating functions
 490   with a primal {Barvinok} algorithm},
 491     author = {Matthias K\"oppe and Sven Verdoolaege},
 492     year = 2008,
 493   journal = {The Electronic Journal of Combinatorics},
 494   volume = 15,
 495   pages = {\#R16}
 496 }
 497
 498 @article{Lepelley2008,
 499     author =       {Dominique Lepelley and Ahmed Louichi and Hatem Smaoui},
 500     title =        {On {Ehrhart} Polynomials and Probability
 501                     Calculations in Voting Theory},
 502     journal =      "Social Choice and Welfare",
 503     year =         {2008},
 504     month =        Apr,
 505     Publisher =    "Springer Berlin / Heidelberg",
 506     ISSN =         "0176-1714 (Print) 1432-217X (Online)",
 507     DOI =           "10.1007/s00355-007-0236-1",
 508     Volume = 30,
 509     Number = 3,
 510     pages = "363-383",
 511 }
 512
 513 @article{Barvinok2006simplex,
 514   author =       {Barvinok, Alexander I.},
 515   title =        {Computing the {Ehrhart} quasi-polynomial of a rational simplex},
 516   year =         2006,
 517   pages =        "1449-1466",
 518   volume =       75,
 519   journal =      "Math. Comp.",
 520   PUBLISHER = {American Mathematical Society},
 521 }
 522
 523 @mastersthesis{Rabl2006,
 524     title = "Volume Calculation and Estimation of Parameterized Integer Polytopes",
 525     author = "Tilmann Rabl",
 526     month = jan,
 527     school = Passau,
 528     year = 2006,
 529 }
 530
 531 @book{ Ehrhart1977,
 532     author = "E. Ehrhart",
 533     title = "Polyn\^omes arithm\'etiques et M\'ethode des Poly\`edres en Combinatoire",
 534     series = "International Series of Numerical Mathematics",
 535     volume = 35,
 536     publisher = "Birkhauser Verlag",
 537     address =  "Basel/Stuttgart",
 538     year = 1977,
 539 }
 540
 541 @book{Stanley1986,
 542     author =       "Richard P. Stanley",
 543     title =        "Enumerative Combinatorics",
 544     volume =     1,
 545     publisher =    "Cambridge University Press",
 546     year = 1986,
 547 }
 548
 549 @misc{Woods2006personal,
 550     author = "Kevin M. Woods",
 551     title = "personal communication",
 552     year = 2006,
 553     month = jun,
 554 }
 555
 556 @Techreport{Pop06,
 557   Author = "S. Pop and G.-A. Silber and A. Cohen and C. Bastoul
 558             and S. Girbal and N. Vasilache",
 559   Title = "{GRAPHITE}: Polyhedral Analyses and Optimizations for {GCC}",
 560   Number = "A/378/CRI",
 561   Institution = "Centre de Recherche en Informatique,
 562                  \'Ecole des Mines de Paris",
 563   Address = "Fontainebleau, France",
 564   Year = 2006,
 565   Note = "Contribution to the GNU Compilers Collection Developers Summit 2006
 566           (GCC Summit 06), Ottawa, Canada, June 28--30, 2006",
 567   Abstract = "We present a plan to add loop nest optimizations in GCC
 568               based on polyhedral representations of loop nests. We
 569               advocate a static analysis approach based on a hierarchy
 570               of interchangeable abstractions with solvers that range
 571               from the exact solvers such as OMEGA, to faster but less
 572               precise solvers based on more coarse abstractions. The
 573               intermediate representation GRAPHITE (GIMPLE Represented
 574               as Polyhedra with Interchangeable Envelopes), built on
 575               GIMPLE and the natural loops, hosts the high level loop
 576               transformations. We base this presentation on the
 577               WRaP-IT project developed in the Alchemy group at INRIA
 578               Futurs and Paris-Sud University, on the PIPS compiler
 579               developed at \'Ecole des mines de Paris, and on a joint
 580               work with several members of the static analysis and
 581               polyhedral compilation community in France.
 582
 583               The main goal of this project is to bring more high
 584               level loop optimizations to GCC: loop fusion, tiling,
 585               strip mining, etc. Thanks to the WRaP-IT experience, we
 586               know that the polyhedral analyzes and transformations
 587               are affordable in a production compiler. A second goal
 588               of this project is to experiment with compile time
 589               reduction versus attainable precision when replacing
 590               operations on polyhedra with faster operations on more
 591               abstract domains. However, the use of a too coarse
 592               representation for computing might also result in an
 593               over approximated solution that cannot be used in
 594               subsequent computations. There exists a trade off
 595               between speed of the computation and the attainable
 596               precision that has not yet been analyzed for real world
 597               programs."
 598 }
 599
 600 @article{Baldoni2006,
 601   author    = {Baldoni-Silva, M. Welleda and
 602                Matthias Beck and
 603                Charles Cochet and
 604                Mich{\`e}le Vergne},
 605   title     = {Volume Computation for Polytopes and Partition Functions
 606                for Classical Root Systems.},
 607   journal   = {Discrete {\&} Computational Geometry},
 608   volume    = {35},
 609   number    = {4},
 610   year      = {2006},
 611   pages     = {551-595},
 612   ee        = {http://dx.doi.org/10.1007/s00454-006-1234-2},
 613   bibsource = {DBLP, http://dblp.uni-trier.de}
 614 }
 615
 616 @inproceedings{Meister2008,
 617   author = {Beno\^it Meister and Sven Verdoolaege},
 618   title = {Polynomial Approximations in the Polytope Model: Bringing the Power
 619   of Quasi-Polynomials to the Masses},
 620   year = {2008},
 621   booktitle = {Digest of the 6th Workshop on Optimization for DSP and Embedded Systems, ODES-6},
 622   editor = "Jagadeesh Sankaran and Vander Aa, Tom",
 623   month = apr,
 624 }
 625
 626 @misc{Devos2007,
 627     title = "Bounds on Quasi-Polynomials for Static Program Analysis",
 628     author = {Harald Devos and Sven Verdoolaege and Van Campenhout, Jan and
 629               Dirk Stroobandt},
 630     year = 2007,
 631     note = "manuscript in preparation",
 632 }
 633
 634 @article{Bueler2000exact,
 635     booktitle = "Polytopes --- Combinatorics and Computation",
 636     editor = "G. Kalai and G. Ziegler",
 637     publisher = {Birkh\"auser-Verlag},
 638     note = "DMV Seminar Band 29",
 639     title = "Exact volume computation for polytopes: A practical study",
 640     year = 2000,
 641     author = {Benno B\"ueler and Andreas Enge and Komei Fukuda},
 642 }
 643
 644 @article{Cohen1979volumes,
 645  author = {Jacques Cohen and Timothy Hickey},
 646  title = {Two Algorithms for Determining Volumes of Convex Polyhedra},
 647  journal = {J. ACM},
 648  volume = {26},
 649  number = {3},
 650  year = {1979},
 651  issn = {0004-5411},
 652  pages = {401--414},
 653  doi = {http://doi.acm.org/10.1145/322139.322141},
 654  publisher = {ACM Press},
 655  address = {New York, NY, USA},
 656 }
 657
 658 @article{Lee1991,
 659     author = "C. W. Lee",
 660     title = "Regular triangulations of convex polytopes",
 661     journal =  "Applied Geometry and Discrete Mathematics --- The Victor Klee Festschrift",
 662     editor = "P. Gritzmann and B. Sturmfels",
 663     series = "DIMACS series in Discrete Math. and Theoretical Comp. Science, 4",
 664     year = 1991,
 665     pages = "443--456",
 666     volume = 4,
 667 }
 668
 669 @PhDThesis{ DeLoera1995,
 670     author = "De Loera, J. A.",
 671     title = "Triangulations of Polytopes and Computational Algebra",
 672     school = "Cornell University",
 673     month =  May,
 674     year = 1995,
 675 }
 676
 677 @book{Henrici1974,
 678     series = "Pure and applied mathematics",
 679     AUTHOR = {Henrici, Peter},
 680      TITLE = {Applied and Computational Complex Analysis},
 681       NOTE = {Volume 1: Power series---integration---conformal
 682               mapping---location of zeros,
 683               Pure and Applied Mathematics},
 684  PUBLISHER = {Wiley-Interscience [John Wiley \& Sons]},
 685    ADDRESS = {New York},
 686       YEAR = {1974},
 687      PAGES = {xv+682},
 688    MRCLASS = {30-02 (65E05)},
 689   MRNUMBER = {MR0372162 (51 \#8378)},
 690 MRREVIEWER = {M. Marden},
 691 }
 692
 693 @article{Barvinok1999,
 694     author = "A. I. Barvinok and J. Pommersheim",
 695     title = "An algorithmic theory of lattice points in polyhedra",
 696     journal = "New Perspectives in Algebraic Combinatorics",
 697     series = "MSRI book series",
 698     volume =  "38",
 699     pages = "91--147",
 700     publisher = "Cambridge University Press, Cambridge",
 701     year = 1999,
 702 }
 703
 704 @Misc{latte-macchiato,
 705   author =       {K\"oppe, Matthias},
 706   title =        {{LattE macchiato}, version 1.2-mk-0.7.1, an improved version of {De Loera}
 707                   et al.'s {LattE} program for counting integer points in
 708                   polyhedra with variants of {Barvinok}'s algorithm},
 709   howpublished = {Available from URL {\url{http://www.math.uni-magdeburg.de/~mkoeppe/latte/}}}
 710 ,
 711   year = 2006
 712 }
 713
 714 @inproceedings{Tawbi1994,
 715     author = "N. Tawbi",
 716     title = "Estimation of Nested Loops execution time by Integer Arithmetic in Convex Polyhedra",
 717     booktitle = "Proceedings of the 8th International Parallel Processing Symposium",
 718     publisher = "IEEE Computer Society Press",
 719     pages =  "217--221",
 720     year = 1994,
 721 }
 722
 723 @inproceedings{Sakellariou1997sums,
 724     author = "Rizos Sakellariou",
 725     title = "Symbolic Evaluation of Sums for Parallelising Compilers",
 726     editor = "A. Sydow",
 727     booktitle = "Proceedings of the 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics",
 728     location = "Berlin",
 729     month = Aug,
 730     year = 1997,
 731     volume = 2,
 732     series = "Wissenschaft \& Technik Verlag",
 733     pages = "685-690",
 734 }
 735
 736 @phdthesis{Sakellariou1996phd,
 737 author =  {R. Sakellariou},
 738 title =   {On the Quest for Perfect Load Balance in Loop-Based Parallel Computations},
 739 school =  {University of Manchester},
 740 year =    {1996},
 741 month =   oct,
 742 }
 743
 744 @article{VanEngelen2004,
 745  author =       {Van Engelen, R. A. and K. Gallivan and B. Walsh},
 746  title =        {Parametric Timing Estimation With the {N}ewton-{G}regory Formulae},
 747  journal =      {Journal of Concurrency and Computation: Practice and Experience},
 748  volume =       {18},
 749  number =       {10},
 750  year =         {2006},
 751  month =        sep,
 752  issn =         {},
 753  pages =        {1434--1464},
 754  publisher =    {Wiley Press, USA},
 755 }
 756
 757 @misc{Berline2006local,
 758     title = "Local {Euler-Maclaurin} formula for polytopes",
 759     author = "Nicole Berline and Mich\`ele Vergne",
 760     year = 2006,
 761     month = jul,
 762     note = "http://arXiv.org/abs/math/0507256",
 763 }
 764
 765 @misc{Berline2007personal,
 766     author = "Nicole Berline",
 767     title = "personal communication",
 768     year = 2007,
 769     month = aug,
 770 }
 771
 772 @inproceedings{Eisenschmidt2007integrally,
 773         author = {Eisenschmidt, Elke and K\"oppe, Matthias},
 774         title = "Integrally  indecomposable polytopes and the survivable network design problem",
 775         note = "To appear",
 776         booktitle = "Electronic proceedings of the 6th International Workshop on the Design of Reliable Communication Networks, DRCN 2007",
 777         locationg = "La Rochelle, France",
 778         year = 2007,
 779 }
 780
 781 @inproceedings{Pfeifle2003,
 782   author    = {Julian Pfeifle and
 783                J{\"o}rg Rambau},
 784   title     = {Computing Triangulations Using Oriented Matroids.},
 785   booktitle = {Algebra, Geometry, and Software Systems},
 786   year      = {2003},
 787   publisher = {Springer},
 788   pages     = {49-75},
 789   editor    = {Michael Joswig and
 790                Nobuki Takayama},
 791 }
 792
 793 @book{Gelfand1994,
 794     author = "I. M. Gelfand and Mikhail Kapranov and A. V. Zelevinsky",
 795     title = "Discriminants, Resultants and Multidimensional Determinants",
 796     publisher = "Birkhauser, Boston",
 797     year = 1994,
 798 }
 799
 800 @PhdThesis{Eisenbrand2000PhD,
 801     author = "F. Eisenbrand",
 802     title = "{Gomory-Chv{\'a}tal} cutting planes and the elementary closure of polyhedra",
 803     school = {Universit\"at des Saarlandes},
 804     month = Jul,
 805     year = 2000,
 806 }
 807
 808 @article{Hung1990,
 809     title = "An application of the Hermite normal form in integer programming",
 810     journal = "Linear Algebra and its Applications",
 811     Volume = 140,
 812     number = 15,
 813     month = Oct,
 814     year = 1990,
 815     Pages = "163--179",
 816     author = "Ming S. Hung and Walter O. Rom",
 817 }
 818
 819 @Misc{4ti2,
 820   author =   {
 821   Ralf Hemmecke and
 822   Raymond Hemmecke and
 823   Matthias K\"oppe and
 824   Peter Malkin and
 825   Matthias Walter},
 826   title =    {4ti2 -- A software package for algebraic, geometric and
 827               combinatorial problems on linear spaces},
 828   howpublished = {Available at \url{www.4ti2.de}}
 829 }
 830
 831 @inproceedings{Hemmecke2002Hilbert,
 832     author = "R. Hemmecke",
 833     title = "On the Computation of Hilbert Bases of Cones",
 834     bookttile = "Mathematical Software, ICMS 2002",
 835     editor = "A. M. Cohen and X.-S. Gao and N. Takayama",
 836     publisher = "World Scientific",
 837     year = 2002,
 838 }
 839
 840 @misc{Eisenbrand2007parameterised,
 841     author = "Friedrich Eisenbrand and Gennady Shmonin",
 842     title = "Parametric integer programming in fixed dimension",
 843     year = 2007,
 844 }
 845
 846 @article{Kannan1992,
 847     author = "R. Kannan",
 848     title = "Lattice translates of a polytope and the {Frobenius} problem",
 849     journal = "Combinatorica",
 850     volume = 12,
 851     number = 2,
 852     pages = "161--177",
 853     year = 1992,
 854 }
 855
 856 @phdthesis{Woods2004PhD,
 857     author = "Woods, Kevin M.",
 858     title = "Rational Generating Functions and Lattice Point Sets",
 859     school = "University of Michigan",
 860     year =  2004,
 861 }
 862
 863 @misc{Koeppe2007personal,
 864     author = {Matthias K\"oppe},
 865     title = "personal communication",
 866     year = 2007,
 867     month = jun,
 868 }
 869
 870 @book {Barvinok02,
 871     AUTHOR = {Barvinok, Alexander},
 872      TITLE = {A {C}ourse in {C}onvexity},
 873     SERIES = {Graduate Studies in Mathematics},
 874     VOLUME = {54},
 875  PUBLISHER = {American Mathematical Society},
 876    ADDRESS = {Providence, RI},
 877       YEAR = {2002},
 878      PAGES = {x+366},
 879       ISBN = {0-8218-2968-8},
 880    MRCLASS = {52-02 (49N15 52-01 90-02 90C05 90C22 90C25)},
 881   MRNUMBER = {2003j:52001},
 882 MRREVIEWER = {P. McMullen},
 883 }
 884
 885 @article{Lagarias90,
 886   author    = {J. C. Lagarias and
 887                Lenstra, Jr., Hendrik W. and
 888                Claus-Peter Schnorr},
 889   title     = {Korkin-Zolotarev bases and successive minima of a lattice
 890                and its reciprocal lattice},
 891   journal   = {Combinatorica},
 892   volume    = {10},
 893   number    = {4},
 894   year      = {1990},
 895   pages     = {333-348},
 896   bibsource = {DBLP, http://dblp.uni-trier.de},
 897 }
 898
 899 @article{Edmonds82,
 900   author    = {J. Edmonds and
 901                L{\'a}szl{\'o} Lov{\'a}sz and
 902                William R. Pulleyblank},
 903   title     = {Brick decompositions and the matching rank of graphs},
 904   journal   = {Combinatorica},
 905   volume    = {2},
 906   number    = {3},
 907   year      = {1982},
 908   pages     = {247-274},
 909   bibsource = {DBLP, http://dblp.uni-trier.de},
 910 }
 911
 912 @article{Cook1992,
 913     author = "Cook, W. and Hartmann, M. and Kannan, R. and McDiarmid, C.",
 914     year = 1992,
 915     title = "On integer points in polyhedra",
 916     journal = "Combinatorica",
 917     volume =  12,
 918     number = 1,
 919     pages = "27--37",
 920 }
 921
 922 @phdthesis{Hartmann1989PhD,
 923  author = {Mark Evan Hartmann},
 924  title = {Cutting planes and the complexity of the integer hull},
 925  year = {1989},
 926  order_no = {AAI8915096},
 927  publisher = {Cornell University},
 928  address = {Ithaca, NY, USA},
 929  }
 930
 931 @inproceedings{Huggins06,
 932   author    = {Peter Huggins},
 933   title     = {{\it iB4e}: A Software Framework for Parametrizing Specialized
 934                {LP} Problems},
 935   booktitle = {ICMS 2006, Proceedings of the Second International
 936                Congress on Mathematical Software},
 937   editor    = {Andr{\'e}s Iglesias and
 938                Nobuki Takayama},
 939   year      = {2006},
 940   pages     = {245-247},
 941   ee        = {http://dx.doi.org/10.1007/11832225_24},
 942   publisher = {Springer},
 943   series    = {Lecture Notes in Computer Science},
 944   volume    = {4151},
 945   bibsource = {DBLP, http://dblp.uni-trier.de},
 946 }
 947
 948 @book{Preparata1985,
 949         abstract = {{From the reviews: "This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry. ... ... The book is well organized and lucidly written; a timely contribution by two founders of the field. It clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics. It also points the way to the solution of the more challenging problems in dimensions higher than two." #Mathematical Reviews#1 "... This remarkable book is a comprehensive and systematic study on research results obtained especially in the last ten years. The very clear presentation concentrates on basic ideas, fundamental combinatorial structures, and crucial algorithmic techniques. The plenty of results is clever organized following these guidelines and within the framework of some detailed case studies. A large number of figures and examples also aid the understanding of the material. Therefore, it can be highly recommended as an early graduate text but it should prove also to be essential to researchers and professionals in applied fields of computer-aided design, computer graphics, and robotics." #Biometrical  Journal#2}},
 950         author = {Preparata, Franco  P.  and Shamos, Michael  I. },
 951         citeulike-article-id = {935971},
 952         howpublished = {Hardcover},
 953         isbn = {0387961313},
 954         keywords = {algorithm, computational, computing, geometry},
 955         month = {August},
 956         priority = {0},
 957         publisher = {Springer},
 958         title = {Computational Geometry: An Introduction (Monographs in Computer Science)},
 959         year = {1985}
 960 }
 961
 962 @article{Woods2005period,
 963         title = "Computing the period of an {Ehrhart} quasi-polynomial",
 964         author = "Kevin M. Woods",
 965         journal = "The Electronic Journal of Combinatorics",
 966         volume = 12,
 967         year = 2005,
 968         pages = "R34",
 969 }
 970
 971 @article{Woods2003short,
 972     year = 2003,
 973     Journal = "J. Amer. Math. Soc.",
 974     volume =  16,
 975     pages = "957--979",
 976     month = apr,
 977     title = {{Short rational generating functions for lattice point
 978         problems}},
 979     author = {Alexander I. Barvinok and Kevin M. Woods},
 980 }
 981
 982 @article{Banaszczyk1999flatness,
 983     title = "The Flatness Theorem for nonsymmetric convex bodies via the local theory of Banach spaces",
 984     author = "Banaszczyk, Wojciech and Litvak, Alexander E. and Pajor, A. and Szarek, S. J.",
 985     journal = "Mathematics of Operations Research",
 986     month =  Aug,
 987     year = 1999,
 988     volume =  24,
 989     number =  3,
 990     pages = "728--750",
 991 }
 992
 993 @inproceedings{ Pugh94counting,
 994     author = "William Pugh",
 995     title = "Counting Solutions to {Presburger} Formulas: How and Why",
 996     booktitle = "{SIGPLAN} Conference on Programming Language Design and Implementation (PLDI'94)",
 997     pages = "121--134",
 998     year = "1994",
 999 }
1000
1001 @inproceedings{Parker2004,
1002     title = "An automata-theoretic algorithm for counting solutions to {Presburger} formulas",
1003     author = "Erin Parker and Siddhartha Chatterjee",
1004     year = 2004,
1005     booktitle = "Compiler Construction 2004",
1006     series =     {Lecture Notes in Computer Science},
1007     volume =    2985,
1008     pages = {104--119},
1009     month = apr,
1010     publisher = "Springer-Verlag",
1011     address = "Berlin",
1012 }
1013
1014 @misc{Baldoni2008,
1015         title = "Sum over lattice points of a polygon with iterated {Laurent} series. User's guide",
1016         author = "Velleda Baldoni and Nicole Berline and Mich\'ele Vergne",
1017         month = mar,
1018         year = 2008,
1019 }
1020
1021 @inproceedings{Koeppe2008implementation,
1022         title = "An Implementation of the Barvinok--Woods Integer Projection Algorithm",
1023         author = {Matthias K\"oppe and Verdoolaege, Sven and Woods, Kevin M.},
1024         year = 2008,
1025         booktitle = "The 2008 International Conference on Information Theory and Statistical Learning",
1026         month = jul,
1027         editor = "Matthias Beck and Thomas Stoll",
1028 }
1029
1030 @inproceedings{Verdoolaege2008weighted,
1031         title = "Algorithms for Weighted Counting over Parametric Polytopes: A Survey and a Practical Comparison",
1032         author = "Verdoolaege, Sven and Bruynooghe, Maurice",
1033         year = 2008,
1034         booktitle = "The 2008 International Conference on Information Theory and Statistical Learning",
1035         month = jul,
1036         editor = "Matthias Beck and Thomas Stoll",
1037 }
1038
1039 @inproceedings{Fukuda2008,
1040  author = {Komei Fukuda},
1041  title = {Exact algorithms and software in optimization and polyhedral computation},
1042  booktitle = {ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation},
1043  year = {2008},
1044  isbn = {978-1-59593-904-3},
1045  pages = {333--334},
1046  location = {Linz/Hagenberg, Austria},
1047  doi = {http://doi.acm.org/10.1145/1390768.1390814},
1048  publisher = {ACM},
1049  address = {New York, NY, USA},
1050 }
1051
1052 @mastersthesis{vanHerick2007,
1053     title = "Theoretical and Computational Methods for Lattice Point Enumeration in Inside-Out Polytopes",
1054     author = "van Herick, Andrew William",
1055     month = jul,
1056     school = "San Francisco State University",
1057     year = 2007,
1058 }
1059
1060 @misc{Baldoni2009,
1061         title = "Summing a polynomial function over integral points of a polygon. User's guide",
1062         author = "Velleda Baldoni and Nicole Berline and Mich\'ele Vergne",
1063         month = may,
1064         year = 2009,
1065 }
1066
1067 @article{Beck2010,
1068         title = "Enumeration of $4 \times 4$ magic squares",
1069         author = "Matthias Beck and van Herick, Andrew William",
1070         Journal = "Math. Comp.",
1071         year = 2010,
1072 }
1073
1074 @inproceedings{Aspinall2010,
1075         author = "David Aspinall and Robert Atkey and Kenneth MacKenzie and Don Sannella",
1076         title = "Symbolic and Analytic Techniques for Resource Analysis of Java Bytecode",
1077         year = 2010,
1078         booktitle = "Trustworthly Global Computing: 5th International Symposium",
1079         pages = "1--22",
1080         publisher = "Springer",
1081 }
1082
1083 @article{Koeppe2010,
1084         author = "M. Koeppe and M. Queyranne and C. T. Ryan",
1085         title = "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs",
1086          Journal = "Journal of Optimization Theory and Applications",
1087          Publisher = "Springer Netherlands",
1088          Volume = 146,
1089          Number = 1,
1090          mont = July,
1091          year = 2010,
1092          DOI = "10.1007/s10957-010-9668-3",
1093          Pages = "137-150",
1094 }
1095
1096 @inproceedings{Ryan2010,
1097  author = {Ryan, Chris T. and Jiang, Albert Xin and Leyton-Brown, Kevin},
1098  title = {Symmetric games with piecewise linear utilities},
1099  booktitle = {BQGT '10: Proceedings of the Behavioral and Quantitative Game Theory},
1100  year = {2010},
1101  isbn = {978-1-60558-919-0},
1102  pages = {1--1},
1103  location = {Newport Beach, California},
1104  doi = {http://doi.acm.org/10.1145/1807406.1807447},
1105  publisher = {ACM},
1106  address = {New York, NY, USA},
1107  }
1108
1109 @inproceedings{Verdoolaege2009equivalence,
1110         author = "Sven Verdoolaege and Gerda Janssens and Maurice Bruynooghe",
1111         title = "Equivalence checking of static affine programs using widening to handle recurrences",
1112         booktitle = "Computer Aided Verification 21",
1113         month = Jun,
1114         year = 2009,
1115         pages = "599--613",
1116         publisher = "Springer",
1117 }
1118
1119 @article{Boulet2001SPPoC,
1120         author = "Pierre Boulet and Xavier Redon",
1121         title = "SPPoC: manipulation automatique de poly\`edres pour la compilation",
1122         journal = "Technique et Science Informatiques",
1123         volume = 20,
1124         number = 8,
1125         year = 2001,
1126         pages = "1019-1048",
1127 }
1128
1129 @article{Hubler2012,
1130         title = "Counting chemical compositions using Ehrhart quasi-polynomials",
1131         abstract = "To count the number of chemical compositions of a particular mass, we consider an alphabet a with a mass function which assigns a mass to each letter in a . We then compute the mass of a word (an ordered sequence of letters) by adding the masses of the constituent letters. Our main interest is to count the number of words that have a particular mass, where we ignore the order of the letters within the word. We show first that counting the number of words of a given mass has a geometric interpretation, whose solutions are called Ehrhart quasi-polynomials, a class of functions defined on integers. These special functions are “periodic” in the sense that they use the same polynomial every λ steps. In addition to discovering the connection between counting compositions and Ehrhart quasi-polynomials, we also find number theoretic results that greatly reduce the number of candidates for the period, λ. Finally, we illustrate the usefulness of these results and the use of a software library named barvinok (by Verdoolaege et al.) by applying them to eight different classes of chemical compositions, including organic molecules, peptides, DNA, and RNA.",
1132         author = "Shane L. Hubler and Gheorghe Craciun",
1133         journal = "Journal of Mathematical Chemistry",
1134         year = 2012,
1135         doi = "10.1007/s10910-012-0042-6",
1136         publisher = {Springer Netherlands},
1137         issn = {0259-9791},
1138         pages = {1-25},
1139 }