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 @MISC{Beck2005Brion,
 290   author = {Matthias Beck and Christian Haase and Frank Sottile},
 291   title = {Theorems of {Brion}, {Lawrence}, and {Varchenko} on rational generating  functions for cones},
 292   url = {http://www.citebase.org/abstract?id=oai:arXiv.org:math/0506466},
 293   year = {2005}
 294 }
 295
 296 @article{Lasserre2005alternative,
 297     author = "Jean B. Lasserre and Eduardo S. Zeron",
 298     title = "An alternative algorithm for counting lattice points in a convex polytope",
 299     year = 2005,
 300     volume = 30,
 301     page = "597--614",
 302     journal = "Math. Oper. Res.",
 303 }
 304
 305 @article{Beyls2005hints,
 306 author= {Beyls, Kristof and  D'Hollander, Erik},
 307 title= {Generating Cache Hints for Improved Program Efficiency},
 308 journal= {Journal of Systems Architecture},
 309 year= {2005},
 310 month= {4},
 311 volume= {51},
 312 number= {4},
 313 pages= {223-250},
 314 publisher= {Elsevier},
 315 }
 316
 317 @TechReport{CFGV06,
 318   author       = {Clauss, P. and Fern\'andez, F. J. and Gabervetsky, D. and Verdoolaege, S.},
 319   title        = {Symbolic Polynomial Maximization over Convex Sets and its Application to Memory Requirement Estimation},
 320   institution  = {Universit\'e Louis Pasteur},
 321   number       = {06-04},
 322   month        = oct,
 323   year         = {2006},
 324   type         = {ICPS Research Report},
 325   url          = {http://icps.u-strasbg.fr/upload/icps-2006-173.pdf},
 326 }
 327
 328 @article{Cook1993implementation,
 329 AUTHOR={William Cook and Thomas Rutherford and Herbert E. Scarf and David F. Shallcross},
 330 TITLE={An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming},
 331 YEAR=1993,
 332 journal = "ORSA Journal on Computing",
 333 volume = 5,
 334 number = 2,
 335 }
 336
 337 @misc{GLPK,
 338 author = "Andrew Makhorin",
 339 title = "GNU Linear Programming Kit, Reference Manual, Version 4.11",
 340 year = 2006,
 341 month = jul,
 342 }
 343
 344 @inproceedings{Verdoolaege2006odes,
 345   AUTHOR = "Verdoolaege, Sven and Nikolov, Hristo and Stefanov, Todor",
 346   TITLE = {Improved Derivation of Process Networks},
 347   YEAR = {2006},
 348   booktitle = {4th Workshop on Optimization for DSP and Embedded Systems, ODES-4},
 349   location = {New York, USA},
 350   month =  mar,
 351 }
 352
 353 @article{Verdoolaege2007pn,
 354   AUTHOR = "Verdoolaege, Sven and Nikolov, Hristo and Stefanov, Todor",
 355   TITLE = {pn: A Tool for Improved Derivation of Process Networks},
 356   YEAR = {2007},
 357   volume = 2007,
 358   journal = "EURASIP Journal on Embedded Systems, special issue on
 359             Embedded Digital Signal Processing Systems",
 360   doi = {10.1155/2007/75947},
 361   publisher = "Hindawi Publishing Corporation",
 362 }
 363
 364 @article{Scarf2006Neighborhood,
 365   author    = {Herbert E. Scarf and
 366                Kevin M. Woods},
 367   title     = {Neighborhood Complexes and Generating Functions for Affine
 368                Semigroups.},
 369   journal   = {Discrete {\&} Computational Geometry},
 370   volume    = {35},
 371   number    = {3},
 372   year      = {2006},
 373   pages     = {385-403},
 374   ee        = {http://dx.doi.org/10.1007/s00454-005-1222-y},
 375   bibsource = {DBLP, http://dblp.uni-trier.de}
 376 }
 377
 378 @ARTICLE{Scarf1981indivisibilities:II,
 379 AUTHOR={Scarf, Herbert E},
 380 TITLE={Production Sets with Indivisibilities-Part {II}: The Case of Two Activities},
 381 JOURNAL={Econometrica},
 382 YEAR=1981,
 383 VOLUME={49},
 384 NUMBER={2},
 385 PAGES={395-423},
 386 MONTH=Mar,
 387 }
 388
 389 @phdthesis{Meister2004PhD,
 390     title = {Stating and Manipulating Periodicity in the Polytope Model. Applications to Program Analysis and Optimization},
 391     author= {Beno\^it Meister},
 392     institution = {Universit\'e Louis Pasteur},
 393     month = Dec,
 394     year  = {2004},
 395     school = ICPS,
 396 }
 397
 398 @article{Feautrier88parametric,
 399     author = "P. Feautrier",
 400     title = "Parametric Integer Programming",
 401     journal = "Operationnelle/Operations Research",
 402     volume = "22",
 403     number = "3",
 404     pages = "243--268",
 405     year = "1988",
 406     url = "citeseer.nj.nec.com/feautrier88parametric.html",
 407 }
 408
 409 @InProceedings{Gomory1963,
 410   author       = "R. E. Gomory",
 411   editor       = "R. L. Graves and P. Wolfe",
 412   booktitle    = "Recent Advances in Mathematical Programming",
 413   title        = "An algorithm for integer solutions to linear programming",
 414   publisher    = "McGraw-Hill",
 415   address      = "New York",
 416   pages        = "269--302",
 417   year         = "1963",
 418 }
 419
 420 @misc{Feautrier:PIP,
 421     author = "Paul Feautrier",
 422     title = "Solving Systems of Affine (In)Equalities: {PIP}'s User's Guide",
 423     year = 2006,
 424 }
 425
 426 @inproceedings{Barvinok1992volume,
 427  author = {Alexander I. Barvinok},
 428  title = {Computing the volume, counting integral points, and exponential sums},
 429  booktitle = {Proceedings of the eighth annual symposium on Computational geometry},
 430  year = {1992},
 431  isbn = {0-89791-517-8},
 432  pages = {161--170},
 433  location = {Berlin, Germany},
 434  doi = {http://doi.acm.org/10.1145/142675.142713},
 435  publisher = {ACM Press},
 436 }
 437
 438 @misc{Koeppe2006experiments,
 439     title = "Experiments with an algebraic scheme for estimating the number of lattice points in polyhedra",
 440     author = {De Loera, Jes\'us A. and Matthias K\"oppe},
 441     year = 2006,
 442     note = "Manuscript in preparation",
 443 }
 444
 445 @article{DeLoera2003effective,
 446     title = "Effective Lattice Point Counting in Rational Convex Polytopes",
 447     author = "De Loera, Jes\'us A. and Raymond Hemmecke and
 448               Jeremiah Tauzer and Ruriko Yoshida",
 449     year = 2004,
 450     journal = "The Journal of Symbolic Computation",
 451     volume = 38,
 452     number = 4,
 453     pages = "1273--1302",
 454     url = "http://www.math.ucdavis.edu/~latte/theory.html",
 455 }
 456
 457 @article{Barvinok1994,
 458     author = "A. I. Barvinok",
 459     title = "Computing the {Ehrhart} polynomial of a convex lattice polytope",
 460     journal = "Dicrete Comput. Geom.",
 461     volume =  12,
 462     year = 1994,
 463     pages = "35--48",
 464 }
 465
 466 @article {Brion88,
 467     AUTHOR = {Brion, Michel},
 468      TITLE = {Points entiers dans les poly\`edres convexes},
 469    JOURNAL = {Ann. Sci. \'Ecole Norm. Sup. (4)},
 470   FJOURNAL = {Annales Scientifiques de l'\'Ecole Normale Sup\'erieure.
 471               Quatri\`eme S\'erie},
 472     VOLUME = {21},
 473       YEAR = {1988},
 474     NUMBER = {4},
 475      PAGES = {653--663},
 476       ISSN = {0012-9593},
 477      CODEN = {ASENAH},
 478    MRCLASS = {52A43 (11H06 12L10 14F12 32C40)},
 479   MRNUMBER = {90d:52020},
 480 MRREVIEWER = {Daniel Barlet},
 481 }
 482
 483 @article{Koeppe2008parametric,
 484     title = {Computing parametric rational generating functions
 485   with a primal {Barvinok} algorithm},
 486     author = {Matthias K\"oppe and Sven Verdoolaege},
 487     year = 2008,
 488   journal = {The Electronic Journal of Combinatorics},
 489   volume = 15,
 490   pages = {\#R16}
 491 }
 492
 493 @article{Lepelley2008,
 494     author =       {Dominique Lepelley and Ahmed Louichi and Hatem Smaoui},
 495     title =        {On {Ehrhart} Polynomials and Probability
 496                     Calculations in Voting Theory},
 497     journal =      "Social Choice and Welfare",
 498     year =         {2008},
 499     month =        Apr,
 500     Publisher =    "Springer Berlin / Heidelberg",
 501     ISSN =         "0176-1714 (Print) 1432-217X (Online)",
 502     DOI =           "10.1007/s00355-007-0236-1",
 503     Volume = 30,
 504     Number = 3,
 505     pages = "363-383",
 506 }
 507
 508 @article{Barvinok2006simplex,
 509   author =       {Barvinok, Alexander I.},
 510   title =        {Computing the {Ehrhart} quasi-polynomial of a rational simplex},
 511   year =         2006,
 512   pages =        "1449-1466",
 513   volume =       75,
 514   journal =      "Math. Comp.",
 515   PUBLISHER = {American Mathematical Society},
 516 }
 517
 518 @mastersthesis{Rabl2006,
 519     title = "Volume Calculation and Estimation of Parameterized Integer Polytopes",
 520     author = "Tilmann Rabl",
 521     month = jan,
 522     school = Passau,
 523     year = 2006,
 524 }
 525
 526 @book{ Ehrhart1977,
 527     author = "E. Ehrhart",
 528     title = "Polyn\^omes arithm\'etiques et M\'ethode des Poly\`edres en Combinatoire",
 529     series = "International Series of Numerical Mathematics",
 530     volume = 35,
 531     publisher = "Birkhauser Verlag",
 532     address =  "Basel/Stuttgart",
 533     year = 1977,
 534 }
 535
 536 @book{Stanley1986,
 537     author =       "Richard P. Stanley",
 538     title =        "Enumerative Combinatorics",
 539     volume =     1,
 540     publisher =    "Cambridge University Press",
 541     year = 1986,
 542 }
 543
 544 @misc{Woods2006personal,
 545     author = "Kevin M. Woods",
 546     title = "personal communication",
 547     year = 2006,
 548     month = jun,
 549 }
 550
 551 @Techreport{Pop06,
 552   Author = "S. Pop and G.-A. Silber and A. Cohen and C. Bastoul
 553             and S. Girbal and N. Vasilache",
 554   Title = "{GRAPHITE}: Polyhedral Analyses and Optimizations for {GCC}",
 555   Number = "A/378/CRI",
 556   Institution = "Centre de Recherche en Informatique,
 557                  \'Ecole des Mines de Paris",
 558   Address = "Fontainebleau, France",
 559   Year = 2006,
 560   Note = "Contribution to the GNU Compilers Collection Developers Summit 2006
 561           (GCC Summit 06), Ottawa, Canada, June 28--30, 2006",
 562   Abstract = "We present a plan to add loop nest optimizations in GCC
 563               based on polyhedral representations of loop nests. We
 564               advocate a static analysis approach based on a hierarchy
 565               of interchangeable abstractions with solvers that range
 566               from the exact solvers such as OMEGA, to faster but less
 567               precise solvers based on more coarse abstractions. The
 568               intermediate representation GRAPHITE (GIMPLE Represented
 569               as Polyhedra with Interchangeable Envelopes), built on
 570               GIMPLE and the natural loops, hosts the high level loop
 571               transformations. We base this presentation on the
 572               WRaP-IT project developed in the Alchemy group at INRIA
 573               Futurs and Paris-Sud University, on the PIPS compiler
 574               developed at \'Ecole des mines de Paris, and on a joint
 575               work with several members of the static analysis and
 576               polyhedral compilation community in France.
 577
 578               The main goal of this project is to bring more high
 579               level loop optimizations to GCC: loop fusion, tiling,
 580               strip mining, etc. Thanks to the WRaP-IT experience, we
 581               know that the polyhedral analyzes and transformations
 582               are affordable in a production compiler. A second goal
 583               of this project is to experiment with compile time
 584               reduction versus attainable precision when replacing
 585               operations on polyhedra with faster operations on more
 586               abstract domains. However, the use of a too coarse
 587               representation for computing might also result in an
 588               over approximated solution that cannot be used in
 589               subsequent computations. There exists a trade off
 590               between speed of the computation and the attainable
 591               precision that has not yet been analyzed for real world
 592               programs."
 593 }
 594
 595 @article{Baldoni2006,
 596   author    = {Baldoni-Silva, M. Welleda and
 597                Matthias Beck and
 598                Charles Cochet and
 599                Mich{\`e}le Vergne},
 600   title     = {Volume Computation for Polytopes and Partition Functions
 601                for Classical Root Systems.},
 602   journal   = {Discrete {\&} Computational Geometry},
 603   volume    = {35},
 604   number    = {4},
 605   year      = {2006},
 606   pages     = {551-595},
 607   ee        = {http://dx.doi.org/10.1007/s00454-006-1234-2},
 608   bibsource = {DBLP, http://dblp.uni-trier.de}
 609 }
 610
 611 @inproceedings{Meister2008,
 612   author = {Beno\^it Meister and Sven Verdoolaege},
 613   title = {Polynomial Approximations in the Polytope Model: Bringing the Power
 614   of Quasi-Polynomials to the Masses},
 615   year = {2008},
 616   booktitle = {Digest of the 6th Workshop on Optimization for DSP and Embedded Systems, ODES-6},
 617   editor = "Jagadeesh Sankaran and Vander Aa, Tom",
 618   month = apr,
 619 }
 620
 621 @misc{Devos2007,
 622     title = "Bounds on Quasi-Polynomials for Static Program Analysis",
 623     author = {Harald Devos and Sven Verdoolaege and Van Campenhout, Jan and
 624               Dirk Stroobandt},
 625     year = 2007,
 626     note = "manuscript in preparation",
 627 }
 628
 629 @article{Bueler2000exact,
 630     booktitle = "Polytopes --- Combinatorics and Computation",
 631     editor = "G. Kalai and G. Ziegler",
 632     publisher = {Birkh\"auser-Verlag},
 633     note = "DMV Seminar Band 29",
 634     title = "Exact volume computation for polytopes: A practical study",
 635     year = 2000,
 636     author = {Benno B\"ueler and Andreas Enge and Komei Fukuda},
 637 }
 638
 639 @article{Cohen1979volumes,
 640  author = {Jacques Cohen and Timothy Hickey},
 641  title = {Two Algorithms for Determining Volumes of Convex Polyhedra},
 642  journal = {J. ACM},
 643  volume = {26},
 644  number = {3},
 645  year = {1979},
 646  issn = {0004-5411},
 647  pages = {401--414},
 648  doi = {http://doi.acm.org/10.1145/322139.322141},
 649  publisher = {ACM Press},
 650  address = {New York, NY, USA},
 651 }
 652
 653 @article{Lee1991,
 654     author = "C. W. Lee",
 655     title = "Regular triangulations of convex polytopes",
 656     journal =  "Applied Geometry and Discrete Mathematics --- The Victor Klee Festschrift",
 657     editor = "P. Gritzmann and B. Sturmfels",
 658     series = "DIMACS series in Discrete Math. and Theoretical Comp. Science, 4",
 659     year = 1991,
 660     pages = "443--456",
 661     volume = 4,
 662 }
 663
 664 @PhDThesis{ DeLoera1995,
 665     author = "De Loera, J. A.",
 666     title = "Triangulations of Polytopes and Computational Algebra",
 667     school = "Cornell University",
 668     month =  May,
 669     year = 1995,
 670 }
 671
 672 @book{Henrici1974,
 673     series = "Pure and applied mathematics",
 674     AUTHOR = {Henrici, Peter},
 675      TITLE = {Applied and Computational Complex Analysis},
 676       NOTE = {Volume 1: Power series---integration---conformal
 677               mapping---location of zeros,
 678               Pure and Applied Mathematics},
 679  PUBLISHER = {Wiley-Interscience [John Wiley \& Sons]},
 680    ADDRESS = {New York},
 681       YEAR = {1974},
 682      PAGES = {xv+682},
 683    MRCLASS = {30-02 (65E05)},
 684   MRNUMBER = {MR0372162 (51 \#8378)},
 685 MRREVIEWER = {M. Marden},
 686 }
 687
 688 @article{Barvinok1999,
 689     author = "A. I. Barvinok and J. Pommersheim",
 690     title = "An algorithmic theory of lattice points in polyhedra",
 691     journal = "New Perspectives in Algebraic Combinatorics",
 692     series = "MSRI book series",
 693     volume =  "38",
 694     pages = "91--147",
 695     publisher = "Cambridge University Press, Cambridge",
 696     year = 1999,
 697 }
 698
 699 @Misc{latte-macchiato,
 700   author =       {K\"oppe, Matthias},
 701   title =        {{LattE macchiato}, version 1.2-mk-0.7.1, an improved version of {De Loera}
 702                   et al.'s {LattE} program for counting integer points in
 703                   polyhedra with variants of {Barvinok}'s algorithm},
 704   howpublished = {Available from URL {\url{http://www.math.uni-magdeburg.de/~mkoeppe/latte/}}}
 705 ,
 706   year = 2006
 707 }
 708
 709 @inproceedings{Tawbi1994,
 710     author = "N. Tawbi",
 711     title = "Estimation of Nested Loops execution time by Integer Arithmetic in Convex Polyhedra",
 712     booktitle = "Proceedings of the 8th International Parallel Processing Symposium",
 713     publisher = "IEEE Computer Society Press",
 714     pages =  "217--221",
 715     year = 1994,
 716 }
 717
 718 @inproceedings{Sakellariou1997sums,
 719     author = "Rizos Sakellariou",
 720     title = "Symbolic Evaluation of Sums for Parallelising Compilers",
 721     editor = "A. Sydow",
 722     booktitle = "Proceedings of the 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics",
 723     location = "Berlin",
 724     month = Aug,
 725     year = 1997,
 726     volume = 2,
 727     series = "Wissenschaft \& Technik Verlag",
 728     pages = "685-690",
 729 }
 730
 731 @phdthesis{Sakellariou1996phd,
 732 author =  {R. Sakellariou},
 733 title =   {On the Quest for Perfect Load Balance in Loop-Based Parallel Computations},
 734 school =  {University of Manchester},
 735 year =    {1996},
 736 month =   oct,
 737 }
 738
 739 @article{VanEngelen2004,
 740  author =       {Van Engelen, R. A. and K. Gallivan and B. Walsh},
 741  title =        {Parametric Timing Estimation With the {N}ewton-{G}regory Formulae},
 742  journal =      {Journal of Concurrency and Computation: Practice and Experience},
 743  volume =       {18},
 744  number =       {10},
 745  year =         {2006},
 746  month =        sep,
 747  issn =         {},
 748  pages =        {1434--1464},
 749  publisher =    {Wiley Press, USA},
 750 }
 751
 752 @misc{Berline2006local,
 753     title = "Local {Euler-Maclaurin} formula for polytopes",
 754     author = "Nicole Berline and Mich\`ele Vergne",
 755     year = 2006,
 756     month = jul,
 757     note = "http://arXiv.org/abs/math/0507256",
 758 }
 759
 760 @misc{Berline2007personal,
 761     author = "Nicole Berline",
 762     title = "personal communication",
 763     year = 2007,
 764     month = aug,
 765 }
 766
 767 @inproceedings{Eisenschmidt2007integrally,
 768         author = {Eisenschmidt, Elke and K\"oppe, Matthias},
 769         title = "Integrally  indecomposable polytopes and the survivable network design problem",
 770         note = "To appear",
 771         booktitle = "Electronic proceedings of the 6th International Workshop on the Design of Reliable Communication Networks, DRCN 2007",
 772         locationg = "La Rochelle, France",
 773         year = 2007,
 774 }
 775
 776 @inproceedings{Pfeifle2003,
 777   author    = {Julian Pfeifle and
 778                J{\"o}rg Rambau},
 779   title     = {Computing Triangulations Using Oriented Matroids.},
 780   booktitle = {Algebra, Geometry, and Software Systems},
 781   year      = {2003},
 782   publisher = {Springer},
 783   pages     = {49-75},
 784   editor    = {Michael Joswig and
 785                Nobuki Takayama},
 786 }
 787
 788 @book{Gelfand1994,
 789     author = "I. M. Gelfand and Mikhail Kapranov and A. V. Zelevinsky",
 790     title = "Discriminants, Resultants and Multidimensional Determinants",
 791     publisher = "Birkhauser, Boston",
 792     year = 1994,
 793 }
 794
 795 @PhdThesis{Eisenbrand2000PhD,
 796     author = "F. Eisenbrand",
 797     title = "{Gomory-Chv{\'a}tal} cutting planes and the elementary closure of polyhedra",
 798     school = {Universit\"at des Saarlandes},
 799     month = Jul,
 800     year = 2000,
 801 }
 802
 803 @article{Hung1990,
 804     title = "An application of the Hermite normal form in integer programming",
 805     journal = "Linear Algebra and its Applications",
 806     Volume = 140,
 807     number = 15,
 808     month = Oct,
 809     year = 1990,
 810     Pages = "163--179",
 811     author = "Ming S. Hung and Walter O. Rom",
 812 }
 813
 814 @Misc{4ti2,
 815   author =   {
 816   Ralf Hemmecke and
 817   Raymond Hemmecke and
 818   Matthias K\"oppe and
 819   Peter Malkin and
 820   Matthias Walter},
 821   title =    {4ti2 -- A software package for algebraic, geometric and
 822               combinatorial problems on linear spaces},
 823   howpublished = {Available at \url{www.4ti2.de}}
 824 }
 825
 826 @inproceedings{Hemmecke2002Hilbert,
 827     author = "R. Hemmecke",
 828     title = "On the Computation of Hilbert Bases of Cones",
 829     bookttile = "Mathematical Software, ICMS 2002",
 830     editor = "A. M. Cohen and X.-S. Gao and N. Takayama",
 831     publisher = "World Scientific",
 832     year = 2002,
 833 }
 834
 835 @misc{Eisenbrand2007parameterised,
 836     author = "Friedrich Eisenbrand and Gennady Shmonin",
 837     title = "Parametric integer programming in fixed dimension",
 838     year = 2007,
 839 }
 840
 841 @article{Kannan1992,
 842     author = "R. Kannan",
 843     title = "Lattice translates of a polytope and the {Frobenius} problem",
 844     journal = "Combinatorica",
 845     volume = 12,
 846     number = 2,
 847     pages = "161--177",
 848     year = 1992,
 849 }
 850
 851 @phdthesis{Woods2004PhD,
 852     author = "Woods, Kevin M.",
 853     title = "Rational Generating Functions and Lattice Point Sets",
 854     school = "University of Michigan",
 855     year =  2004,
 856 }
 857
 858 @misc{Koeppe2007personal,
 859     author = {Matthias K\"oppe},
 860     title = "personal communication",
 861     year = 2007,
 862     month = jun,
 863 }
 864
 865 @book {Barvinok02,
 866     AUTHOR = {Barvinok, Alexander},
 867      TITLE = {A {C}ourse in {C}onvexity},
 868     SERIES = {Graduate Studies in Mathematics},
 869     VOLUME = {54},
 870  PUBLISHER = {American Mathematical Society},
 871    ADDRESS = {Providence, RI},
 872       YEAR = {2002},
 873      PAGES = {x+366},
 874       ISBN = {0-8218-2968-8},
 875    MRCLASS = {52-02 (49N15 52-01 90-02 90C05 90C22 90C25)},
 876   MRNUMBER = {2003j:52001},
 877 MRREVIEWER = {P. McMullen},
 878 }
 879
 880 @article{Lagarias90,
 881   author    = {J. C. Lagarias and
 882                Lenstra, Jr., Hendrik W. and
 883                Claus-Peter Schnorr},
 884   title     = {Korkin-Zolotarev bases and successive minima of a lattice
 885                and its reciprocal lattice},
 886   journal   = {Combinatorica},
 887   volume    = {10},
 888   number    = {4},
 889   year      = {1990},
 890   pages     = {333-348},
 891   bibsource = {DBLP, http://dblp.uni-trier.de},
 892 }
 893
 894 @article{Edmonds82,
 895   author    = {J. Edmonds and
 896                L{\'a}szl{\'o} Lov{\'a}sz and
 897                William R. Pulleyblank},
 898   title     = {Brick decompositions and the matching rank of graphs},
 899   journal   = {Combinatorica},
 900   volume    = {2},
 901   number    = {3},
 902   year      = {1982},
 903   pages     = {247-274},
 904   bibsource = {DBLP, http://dblp.uni-trier.de},
 905 }
 906
 907 @article{Cook1992,
 908     author = "Cook, W. and Hartmann, M. and Kannan, R. and McDiarmid, C.",
 909     year = 1992,
 910     title = "On integer points in polyhedra",
 911     journal = "Combinatorica",
 912     volume =  12,
 913     number = 1,
 914     pages = "27--37",
 915 }
 916
 917 @phdthesis{Hartmann1989PhD,
 918  author = {Mark Evan Hartmann},
 919  title = {Cutting planes and the complexity of the integer hull},
 920  year = {1989},
 921  order_no = {AAI8915096},
 922  publisher = {Cornell University},
 923  address = {Ithaca, NY, USA},
 924  }
 925
 926 @inproceedings{Huggins06,
 927   author    = {Peter Huggins},
 928   title     = {{\it iB4e}: A Software Framework for Parametrizing Specialized
 929                {LP} Problems},
 930   booktitle = {ICMS 2006, Proceedings of the Second International
 931                Congress on Mathematical Software},
 932   editor    = {Andr{\'e}s Iglesias and
 933                Nobuki Takayama},
 934   year      = {2006},
 935   pages     = {245-247},
 936   ee        = {http://dx.doi.org/10.1007/11832225_24},
 937   publisher = {Springer},
 938   series    = {Lecture Notes in Computer Science},
 939   volume    = {4151},
 940   bibsource = {DBLP, http://dblp.uni-trier.de},
 941 }
 942
 943 @book{Preparata1985,
 944         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}},
 945         author = {Preparata, Franco  P.  and Shamos, Michael  I. },
 946         citeulike-article-id = {935971},
 947         howpublished = {Hardcover},
 948         isbn = {0387961313},
 949         keywords = {algorithm, computational, computing, geometry},
 950         month = {August},
 951         priority = {0},
 952         publisher = {Springer},
 953         title = {Computational Geometry: An Introduction (Monographs in Computer Science)},
 954         year = {1985}
 955 }
 956
 957 @article{Woods2005period,
 958         title = "Computing the period of an {Ehrhart} quasi-polynomial",
 959         author = "Kevin M. Woods",
 960         journal = "The Electronic Journal of Combinatorics",
 961         volume = 12,
 962         year = 2005,
 963         pages = "R34",
 964 }
 965
 966 @article{Woods2003short,
 967     year = 2003,
 968     Journal = "J. Amer. Math. Soc.",
 969     volume =  16,
 970     pages = "957--979",
 971     month = apr,
 972     title = {{Short rational generating functions for lattice point
 973         problems}},
 974     author = {Alexander I. Barvinok and Kevin M. Woods},
 975 }
 976
 977 @article{Banaszczyk1999flatness,
 978     title = "The Flatness Theorem for nonsymmetric convex bodies via the local theory of Banach spaces",
 979     author = "Banaszczyk, Wojciech and Litvak, Alexander E. and Pajor, A. and Szarek, S. J.",
 980     journal = "Mathematics of Operations Research",
 981     month =  Aug,
 982     year = 1999,
 983     volume =  24,
 984     number =  3,
 985     pages = "728--750",
 986 }
 987
 988 @inproceedings{ Pugh94counting,
 989     author = "William Pugh",
 990     title = "Counting Solutions to {Presburger} Formulas: How and Why",
 991     booktitle = "{SIGPLAN} Conference on Programming Language Design and Implementation (PLDI'94)",
 992     pages = "121--134",
 993     year = "1994",
 994 }
 995
 996 @inproceedings{Parker2004,
 997     title = "An automata-theoretic algorithm for counting solutions to {Presburger} formulas",
 998     author = "Erin Parker and Siddhartha Chatterjee",
 999     year = 2004,
1000     booktitle = "Compiler Construction 2004",
1001     series =     {Lecture Notes in Computer Science},
1002     volume =    2985,
1003     pages = {104--119},
1004     month = apr,
1005     publisher = "Springer-Verlag",
1006     address = "Berlin",
1007 }
1008
1009 @misc{Baldoni2008,
1010         title = "Sum over lattice points of a polygon with iterated {Laurent} series. User's guide",
1011         author = "Velleda Baldoni and Nicole Berline and Mich\'ele Vergne",
1012         month = mar,
1013         year = 2008,
1014 }
1015
1016 @inproceedings{Koeppe2008implementation,
1017         title = "An Implementation of the Barvinok--Woods Integer Projection Algorithm",
1018         author = {Matthias K\"oppe and Verdoolaege, Sven and Woods, Kevin M.},
1019         year = 2008,
1020         booktitle = "The 2008 International Conference on Information Theory and Statistical Learning",
1021         month = jul,
1022         editor = "Matthias Beck and Thomas Stoll",
1023 }
1024
1025 @inproceedings{Verdoolaege2008weighted,
1026         title = "Algorithms for Weighted Counting over Parametric Polytopes: A Survey and a Practical Comparison",
1027         author = "Verdoolaege, Sven and Bruynooghe, Maurice",
1028         year = 2008,
1029         booktitle = "The 2008 International Conference on Information Theory and Statistical Learning",
1030         month = jul,
1031         editor = "Matthias Beck and Thomas Stoll",
1032 }