1 @string
(ICPS
= "ICPS
, Universit\'e Louis Pasteur de Strasbourg
, France"
)
2 @string
(Passau
= {Universit\"at Passau
})
4 @techreport
{ Wilde1993
,
5 author = "D. K. Wilde"
,
6 title = "A Library for doing polyhedral operations"
,
8 institution = "IRISA
, Rennes
, France"
,
11 url
= "citeseer.nj.nec.com
/article
/wilde93library.html"
,
12 note = "\\http
://www.irisa.fr
/EXTERNE
/bibli
/pi
/pi785.html"
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"
,
24 publisher = {Kluwer Academic Publishers
},
25 url
= "citeseer.nj.nec.com
/article
/loechner95parameterized.html"
}
27 @TechReport
{ Loechner1999
,
28 author = "Vincent Loechner"
,
31 title = "PolyLib
: A Library for Manipulating Parameterized Polyhedra"
,
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"
,
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"
,
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"
,
61 note = "program available from http
://www.ifor.math.ethz.ch
/~fukuda
/fukuda.html"
,
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"
,
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
},
81 sourceURL
= {ftp
://ftp.wi.leidenuniv.nl
/pub
/CS
/PhDTheses
/bik
-96.ps.gz
},
83 TOPICS
= {Sparse Arrays
}
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
},
92 ADDRESS
= {Leuven
, Belgium
},
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"
,
101 note = {software package
{\tt LattE
} is available at
{\tt http
://www.math.ucdavis.edu
/$\sim$latte
/}},
105 author = "Victor Shoup"
,
107 note = "Available from
{\tt http
://www.shoup.net
/ntl
/}"
,
111 @incollection
{polymake
,
112 author = {Ewgenij Gawrilow and Michael Joswig
},
113 title = {polymake
: a Framework for Analyzing Convex Polytopes
},
115 editor = {Gil Kalai and G\"unter M. Ziegler
},
116 booktitle = {Polytopes
--- Combinatorics and Computation
},
117 publisher = {Birkh\"auser
},
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
},
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"
,
135 institution = "University of Maryland"
,
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"
,
143 institution = "University of Maryland"
,
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"
,
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.
},
165 doi
= {http
://dx.doi.org
/10.1023/A
:1013535431127},
166 publisher = {Kluwer Academic Publishers
},
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
},
173 booktitle = {2nd Workshop on Optimization for DSP and Embedded Systems
, ODES
-2},
174 location
= {Palo Alto
, USA
},
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
},
185 ADDRESS
= {Leuven
, Belgium
},
187 NOTE
= {URL
= http
://www.cs.kuleuven.ac.be
/publicaties
/rapporten
/cw
/CW376.abs.html
},
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
},
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
}.
},
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
},
216 NOTE
= {URL
= http
://www.cs.kuleuven.ac.be
/publicaties
/rapporten
/cw
/CW395.abs.html
},
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
},
224 EDITOR
= {Bodik
, R.
},
227 series = "Lecture Notes in Computer Science"
,
228 publisher = "Springer
-Verlag"
,
232 @TECHREPORT
{Verdoolaege2005barvinok
,
233 AUTHOR
= "Verdoolaege
, Sven and Woods
, Kevin M. and Bruynooghe
, Maurice and
236 TITLE
= {Computation and Manipulation of Enumerators of Integer Projections of
237 Parametric Polytopes
},
240 INSTITUTION
= {Dept.\ of Computer Science
, K.U.Leuven
},
241 ADDRESS
= {Leuven
, Belgium
},
244 @article
{Verdoolaege2008counting
,
245 author = {Sven Verdoolaege and Kevin M. Woods
},
246 title = {Counting with rational generating functions
},
247 journal = {J. Symb. Comput.
},
253 doi
= {http
://dx.doi.org
/10.1016/j.jsc
.2007.07.007},
254 publisher = {Academic Press
, Inc.
},
255 address = {Duluth
, MN
, USA
},
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"
,
266 publisher = "Springer New York"
,
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
},
278 @article
{Koeppe2006primal
,
279 title = {{A primal Barvinok algorithm based on irrational decompositions
}},
280 author = {Matthias K\"oppe
},
282 journal = {SIAM Journal on Discrete Mathematics
},
286 doi
= {10.1137/060664768},
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},
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"
,
302 journal = "Math. Oper. Res."
,
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
},
314 publisher= {Elsevier
},
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
},
324 type = {ICPS Research Report
},
325 url
= {http
://icps.u
-strasbg.fr
/upload
/icps
-2006-173.pdf
},
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
},
332 journal = "ORSA Journal on Computing"
,
338 author = "Andrew Makhorin"
,
339 title = "GNU Linear Programming Kit
, Reference Manual
, Version
4.11"
,
344 @inproceedings
{Verdoolaege2006odes
,
345 AUTHOR
= "Verdoolaege
, Sven and Nikolov
, Hristo and Stefanov
, Todor"
,
346 TITLE
= {Improved Derivation of Process Networks
},
348 booktitle = {4th Workshop on Optimization for DSP and Embedded Systems
, ODES
-4},
349 location
= {New York
, USA
},
353 @article
{Verdoolaege2007pn
,
354 AUTHOR
= "Verdoolaege
, Sven and Nikolov
, Hristo and Stefanov
, Todor"
,
355 TITLE
= {pn
: A Tool for Improved Derivation of Process Networks
},
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"
,
364 @article
{Scarf2006Neighborhood
,
365 author = {Herbert E. Scarf and
367 title = {Neighborhood Complexes and Generating Functions for Affine
369 journal = {Discrete
{\
&} Computational Geometry
},
374 ee
= {http
://dx.doi.org
/10.1007/s00454
-005-1222-y
},
375 bibsource
= {DBLP
, http
://dblp.uni
-trier.de
}
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
},
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
},
398 @article
{Feautrier88parametric
,
399 author = "P. Feautrier"
,
400 title = "Parametric Integer Programming"
,
401 journal = "Operationnelle
/Operations Research"
,
406 url
= "citeseer.nj.nec.com
/feautrier88parametric.html"
,
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"
,
421 author = "Paul Feautrier"
,
422 title = "Solving Systems of Affine
(In
)Equalities
: {PIP
}'s User's Guide"
,
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
},
431 isbn
= {0-89791-517-8},
433 location
= {Berlin
, Germany
},
434 doi
= {http
://doi.acm.org
/10.1145/142675.142713},
435 publisher = {ACM Press
},
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
},
442 note = "Manuscript in preparation"
,
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"
,
450 journal = "The Journal of Symbolic Computation"
,
453 pages = "
1273--1302"
,
454 url
= "http
://www.math.ucdavis.edu
/~latte
/theory.html"
,
457 @article
{Barvinok1994
,
458 author = "A. I. Barvinok"
,
459 title = "Computing the
{Ehrhart
} polynomial of a convex lattice polytope"
,
460 journal = "Dicrete Comput. Geom."
,
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
},
478 MRCLASS
= {52A43
(11H06
12L10 14F12
32C40
)},
479 MRNUMBER
= {90d
:52020},
480 MRREVIEWER
= {Daniel Barlet
},
483 @article
{Koeppe2008parametric
,
484 title = {Computing parametric rational generating functions
485 with a primal
{Barvinok
} algorithm
},
486 author = {Matthias K\"oppe and Sven Verdoolaege
},
488 journal = {The Electronic Journal of Combinatorics
},
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"
,
500 Publisher
= "Springer Berlin
/ Heidelberg"
,
501 ISSN
= "
0176-1714 (Print
) 1432-217X
(Online
)"
,
502 DOI
= "
10.1007/s00355
-007-0236-1"
,
508 @article
{Barvinok2006simplex
,
509 author = {Barvinok
, Alexander I.
},
510 title = {Computing the
{Ehrhart
} quasi
-polynomial of a rational simplex
},
514 journal = "Math. Comp."
,
515 PUBLISHER
= {American Mathematical Society
},
518 @mastersthesis
{Rabl2006
,
519 title = "Volume Calculation and Estimation of Parameterized Integer Polytopes"
,
520 author = "Tilmann Rabl"
,
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"
,
531 publisher = "Birkhauser Verlag"
,
532 address = "Basel
/Stuttgart"
,
537 author = "Richard P. Stanley"
,
538 title = "Enumerative Combinatorics"
,
540 publisher = "Cambridge University Press"
,
544 @misc
{Woods2006personal
,
545 author = "Kevin M. Woods"
,
546 title = "personal communication"
,
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"
,
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.
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
595 @article
{Baldoni2006
,
596 author = {Baldoni
-Silva
, M. Welleda and
600 title = {Volume Computation for Polytopes and Partition Functions
601 for Classical Root Systems.
},
602 journal = {Discrete
{\
&} Computational Geometry
},
607 ee
= {http
://dx.doi.org
/10.1007/s00454
-006-1234-2},
608 bibsource
= {DBLP
, http
://dblp.uni
-trier.de
}
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
},
616 booktitle = {Digest of the
6th Workshop on Optimization for DSP and Embedded Systems
, ODES
-6},
617 editor = "Jagadeesh Sankaran and Vander Aa
, Tom"
,
622 title = "Bounds on Quasi
-Polynomials for Static Program Analysis"
,
623 author = {Harald Devos and Sven Verdoolaege and Van Campenhout
, Jan and
626 note = "manuscript in preparation"
,
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"
,
636 author = {Benno B\"ueler and Andreas Enge and Komei Fukuda
},
639 @article
{Cohen1979volumes
,
640 author = {Jacques Cohen and Timothy Hickey
},
641 title = {Two Algorithms for Determining Volumes of Convex Polyhedra
},
648 doi
= {http
://doi.acm.org
/10.1145/322139.322141},
649 publisher = {ACM Press
},
650 address = {New York
, NY
, USA
},
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"
,
664 @PhDThesis
{ DeLoera1995
,
665 author = "De Loera
, J. A."
,
666 title = "Triangulations of Polytopes and Computational Algebra"
,
667 school = "Cornell University"
,
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
},
683 MRCLASS
= {30-02 (65E05
)},
684 MRNUMBER
= {MR0372162
(51 \#
8378)},
685 MRREVIEWER
= {M. Marden
},
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"
,
695 publisher = "Cambridge University Press
, Cambridge"
,
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
/}}}
709 @inproceedings
{Tawbi1994
,
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"
,
718 @inproceedings
{Sakellariou1997sums
,
719 author = "Rizos Sakellariou"
,
720 title = "Symbolic Evaluation of Sums for Parallelising Compilers"
,
722 booktitle = "Proceedings of the
15th IMACS World Congress on Scientific Computation
, Modelling and Applied Mathematics"
,
727 series = "Wissenschaft \
& Technik Verlag"
,
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
},
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
},
748 pages = {1434--1464},
749 publisher = {Wiley Press
, USA
},
752 @misc
{Berline2006local
,
753 title = "Local
{Euler
-Maclaurin
} formula for polytopes"
,
754 author = "Nicole Berline and Mich\`ele Vergne"
,
757 note = "http
://arXiv.org
/abs
/math
/0507256"
,
760 @misc
{Berline2007personal
,
761 author = "Nicole Berline"
,
762 title = "personal communication"
,
767 @inproceedings
{Eisenschmidt2007integrally
,
768 author = {Eisenschmidt
, Elke and K\"oppe
, Matthias
},
769 title = "Integrally indecomposable polytopes and the survivable network design problem"
,
771 booktitle = "Electronic proceedings of the
6th International Workshop on the Design of Reliable Communication Networks
, DRCN
2007"
,
772 locationg
= "La Rochelle
, France"
,
776 @inproceedings
{Pfeifle2003
,
777 author = {Julian Pfeifle and
779 title = {Computing Triangulations Using Oriented Matroids.
},
780 booktitle = {Algebra
, Geometry
, and Software Systems
},
782 publisher = {Springer
},
784 editor = {Michael Joswig and
789 author = "I. M. Gelfand and Mikhail Kapranov and A. V. Zelevinsky"
,
790 title = "Discriminants
, Resultants and Multidimensional Determinants"
,
791 publisher = "Birkhauser
, Boston"
,
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
},
804 title = "An application of the Hermite normal form in integer programming"
,
805 journal = "Linear Algebra and its Applications"
,
811 author = "Ming S. Hung and Walter O. Rom"
,
821 title = {4ti2
-- A software package for algebraic
, geometric and
822 combinatorial problems on linear spaces
},
823 howpublished = {Available at \url
{www
.4ti2.de
}}
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"
,
835 @misc
{Eisenbrand2007parameterised
,
836 author = "Friedrich Eisenbrand and Gennady Shmonin"
,
837 title = "Parametric integer programming in fixed dimension"
,
842 author = "R. Kannan"
,
843 title = "Lattice translates of a polytope and the
{Frobenius
} problem"
,
844 journal = "Combinatorica"
,
851 @phdthesis
{Woods2004PhD
,
852 author = "Woods
, Kevin M."
,
853 title = "Rational Generating Functions and Lattice Point Sets"
,
854 school = "University of Michigan"
,
858 @misc
{Koeppe2007personal
,
859 author = {Matthias K\"oppe
},
860 title = "personal communication"
,
866 AUTHOR
= {Barvinok
, Alexander
},
867 TITLE
= {A
{C
}ourse in
{C
}onvexity
},
868 SERIES
= {Graduate Studies in Mathematics
},
870 PUBLISHER
= {American Mathematical Society
},
871 ADDRESS
= {Providence
, RI
},
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
},
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
},
891 bibsource
= {DBLP
, http
://dblp.uni
-trier.de
},
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
},
904 bibsource
= {DBLP
, http
://dblp.uni
-trier.de
},
908 author = "Cook
, W. and Hartmann
, M. and Kannan
, R. and McDiarmid
, C."
,
910 title = "On integer points in polyhedra"
,
911 journal = "Combinatorica"
,
917 @phdthesis
{Hartmann1989PhD
,
918 author = {Mark Evan Hartmann
},
919 title = {Cutting planes and the complexity of the integer hull
},
921 order_no
= {AAI8915096
},
922 publisher = {Cornell University
},
923 address = {Ithaca
, NY
, USA
},
926 @inproceedings
{Huggins06
,
927 author = {Peter Huggins
},
928 title = {{\it iB4e
}: A Software Framework for Parametrizing Specialized
930 booktitle = {ICMS
2006, Proceedings of the Second International
931 Congress on Mathematical Software
},
932 editor = {Andr
{\'e
}s Iglesias and
936 ee
= {http
://dx.doi.org
/10.1007/11832225_24
},
937 publisher = {Springer
},
938 series = {Lecture Notes in Computer Science
},
940 bibsource
= {DBLP
, http
://dblp.uni
-trier.de
},
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
},
949 keywords = {algorithm
, computational
, computing
, geometry
},
952 publisher = {Springer
},
953 title = {Computational Geometry
: An Introduction
(Monographs in Computer Science
)},
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"
,
966 @article
{Woods2003short
,
968 Journal
= "J. Amer. Math. Soc."
,
972 title = {{Short rational generating functions for lattice point
974 author = {Alexander I. Barvinok and Kevin M. Woods
},
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"
,
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)"
,
996 @inproceedings
{Parker2004
,
997 title = "An automata
-theoretic algorithm for counting solutions to
{Presburger
} formulas"
,
998 author = "Erin Parker and Siddhartha Chatterjee"
,
1000 booktitle = "Compiler Construction
2004"
,
1001 series = {Lecture Notes in Computer Science
},
1005 publisher = "Springer
-Verlag"
,
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"
,