barvinok_enumerate: integrate barvinok_series
[barvinok.git] / doc / applications.tex
blob61cd68b52ca56f42109765fda0864ec239ca07f1
1 \section{\texorpdfstring{Applications included
2 in the \protect\ai[\tt]{barvinok} distribution}
3 {Applications included in the barvinok distribution}}
4 \label{a:usage}
6 \index{barvinok@{\tt barvinok}!availability}
7 {\sloppy
8 This section describes some application programs
9 provided by the \barvinok/ library,
10 available from {\tt http://freshmeat.net/projects/barvinok/.}
11 For compilation instructions we refer to the \verb+README+ file
12 included in the distribution.
15 Common option to all programs:\\
16 \begin{tabular}{lll}
17 \ai[\tt]{--version} & \ai[\tt]{-V} & print version
18 \end{tabular}
20 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_count}}{barvinok\_count}}
22 The program \ai[\tt]{barvinok\_count} enumerates a
23 non-parametric polytope. It takes one polytope
24 in \PolyLib/ notation as input and prints the number
25 of integer points in the polytope.
26 The \PolyLib/ notation corresponds to the internal
27 representation of \ai[\tt]{Polyhedron}s as explained
28 in Section~\ref{a:existing}.
29 \index{input format!constraints}
30 The first line of the input contains the number of rows
31 and the number of columns in the \ai[\tt]{Constraint} matrix.
32 The rest of the input is composed of the elements of the matrix.
33 Recall that the number of columns is two more than the number
34 of variables, where the extra first columns is one or zero
35 depending on whether the constraint is an inequality ($\ge 0$)
36 or an equality ($= 0$). The next columns contain
37 the coefficients of the variables and the final column contains
38 the constant in the constraint.
39 E.g., the set
40 $S = \lb\, s \mid s \geq 0 \wedge 2 s \leq 13 \, \rb$
41 from \citeN[Example~38 on page~134]{Verdoolaege2005PhD}
42 corresponds to the following input and
43 output.
44 \begin{verbatim}
45 > cat S
46 2 3
48 1 1 0
49 1 -2 13
50 > ./barvinok_count < S
51 POLYHEDRON Dimension:1
52 Constraints:2 Equations:0 Rays:2 Lines:0
53 Constraints 2 3
54 Inequality: [ 1 0 ]
55 Inequality: [ -2 13 ]
56 Rays 2 3
57 Vertex: [ 0 ]/1
58 Vertex: [ 13 ]/2
60 \end{verbatim}
61 \index{PolyLib@{\tt PolyLib}!version 5.22.0 or newer}
62 Note that if you use \PolyLib/ version 5.22.0 or newer then the output
63 may look slightly different as the computation of the \ai[\tt]{Rays}
64 may have been postponed to a later stage.
65 The program \ai[\tt]{latte2polylib.pl} can be used to
66 convert a polytope from \ai[\tt]{LattE} \shortcite{latte1.1}
67 notation to \PolyLib/ notation.
69 \index{input format!vertices}
70 As an alternative to the constraints based input, the input polytope
71 may also be specified by its \ai[\tt]{Ray} matrix.
72 The first line of the input contains the single word \ai[\tt]{vertices}.
73 The second line contains the number of rows
74 and the number of columns in the \ai[\tt]{Ray} matrix.
75 The rest of the input is composed of the elements of the matrix.
76 Recall that the number of columns is two more than the number
77 of variables, where the extra first columns is one or zero
78 depending on whether the ray is a line or not.
79 The next columns contain
80 the numerators of the coordinates and the final column contains
81 the denominator of the vertex or $0$ for a ray.
82 E.g., the above set can also be described as
83 \begin{verbatim}
84 vertices
86 2 3
88 1 0 1
89 1 13 2
90 \end{verbatim}
92 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate}}
93 {barvinok\_enumerate}}
95 The program \ai[\tt]{barvinok\_enumerate} enumerates a
96 parametric polytope as a \psp/ or \rgf/. It takes two polytopes in \PolyLib/
97 notation as input, optionally followed by a list of parameter
98 names.
99 The two polytopes refer to arguments \verb+P+ and \verb+C+
100 of the corresponding function. (See Section~\ref{a:counting:functions}.)
101 The following example was taken by \shortciteN{Loechner1999}
102 from \shortciteN[Chapter II.2]{Loechner97phd}.
103 \begin{verbatim}
104 > cat loechner
105 # Dimension of the matrix:
106 7 7
107 # Constraints:
108 # i j k P Q cte
109 1 1 0 0 0 0 0 # 0 <= i
110 1 -1 0 0 1 0 0 # i <= P
111 1 0 1 0 0 0 0 # 0 <= j
112 1 1 -1 0 0 0 0 # j <= i
113 1 0 0 1 0 0 0 # 0 <= k
114 1 1 -1 -1 0 0 0 # k <= i-j
115 0 1 1 1 0 -1 0 # Q = i + j + k
117 # 2 parameters, no constraints.
119 > ./barvinok_enumerate < loechner
120 POLYHEDRON Dimension:5
121 Constraints:6 Equations:1 Rays:5 Lines:0
122 Constraints 6 7
123 Equality: [ 1 1 1 0 -1 0 ]
124 Inequality: [ 0 1 1 1 -1 0 ]
125 Inequality: [ 0 1 0 0 0 0 ]
126 Inequality: [ 0 0 1 0 0 0 ]
127 Inequality: [ 0 -2 -2 0 1 0 ]
128 Inequality: [ 0 0 0 0 0 1 ]
129 Rays 5 7
130 Ray: [ 1 0 1 1 2 ]
131 Ray: [ 1 1 0 1 2 ]
132 Vertex: [ 0 0 0 0 0 ]/1
133 Ray: [ 0 0 0 1 0 ]
134 Ray: [ 1 0 0 1 1 ]
135 POLYHEDRON Dimension:2
136 Constraints:1 Equations:0 Rays:3 Lines:2
137 Constraints 1 4
138 Inequality: [ 0 0 1 ]
139 Rays 3 4
140 Line: [ 1 0 ]
141 Line: [ 0 1 ]
142 Vertex: [ 0 0 ]/1
143 - P + Q >= 0
144 2P - Q >= 0
145 1 >= 0
147 ( -1/2 * P^2 + ( 1 * Q + 1/2 )
148 * P + ( -3/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 )
149 } + 1/4 )
150 * Q + ( -5/4 * {( 1/2 * Q + 0 )
151 } + 1 )
154 Q >= 0
155 P - Q -1 >= 0
156 1 >= 0
158 ( 1/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 )
159 } + 3/4 )
160 * Q + ( -5/4 * {( 1/2 * Q + 0 )
161 } + 1 )
163 \end{verbatim}
164 The output corresponds to
166 \begin{cases}
167 \makebox[0pt][l]{$-\frac 1 2 P^2 + P Q + \frac 1 2 P - \frac 3 8 Q^2
168 + \left( \frac 1 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right)
169 Q + 1
170 - \frac 5 4 \left\{ \frac 1 2 Q \right\}$} \\
172 \hbox{if $P \le Q \le 2 P$}
174 \frac 1 8 Q^2 +
175 \left( \frac 3 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right)
176 - \frac 5 4 \left\{ \frac 1 2 Q \right\}
177 \qquad
178 \qquad
179 \qquad
180 \qquad
181 \qquad
183 \hbox{if $0 \le Q \le P-1$}
185 \end{cases}
187 The following is an example of Petr Lison\u{e}k\index{Lison\u{e}k, P.}.
188 \begin{verbatim}
189 > cat petr
191 1 -1 -1 -1 1 0
192 1 1 -1 0 0 0
193 1 0 1 -1 0 0
194 1 0 0 1 0 -1
198 > ./barvinok_enumerate --series < petr
199 POLYHEDRON Dimension:4
200 Constraints:5 Equations:0 Rays:5 Lines:0
201 Constraints 5 6
202 Inequality: [ -1 -1 -1 1 0 ]
203 Inequality: [ 1 -1 0 0 0 ]
204 Inequality: [ 0 1 -1 0 0 ]
205 Inequality: [ 0 0 1 0 -1 ]
206 Inequality: [ 0 0 0 0 1 ]
207 Rays 5 6
208 Ray: [ 1 1 1 3 ]
209 Ray: [ 1 1 0 2 ]
210 Ray: [ 1 0 0 1 ]
211 Ray: [ 0 0 0 1 ]
212 Vertex: [ 1 1 1 3 ]/1
213 POLYHEDRON Dimension:1
214 Constraints:1 Equations:0 Rays:2 Lines:1
215 Constraints 1 3
216 Inequality: [ 0 1 ]
217 Rays 2 3
218 Line: [ 1 ]
219 Vertex: [ 0 ]/1
220 (n^3)/((1-n) * (1-n) * (1-n^2) * (1-n^3))
221 \end{verbatim}
223 Options:\\
224 \begin{tabular}{llp{0.7\textwidth}}
225 \ai[\tt]{--floor} & \ai[\tt]{-f} &
226 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
228 \ai[\tt]{--convert} & \ai[\tt]{-c} &
229 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
231 \ai[\tt]{--series} & \ai[\tt]{-s} &
232 compute \rgf/ instead of \psp/
234 \ai[\tt]{--explicit} & \ai[\tt]{-e} &
235 convert computed \rgf/ to a \psp/
236 \end{tabular}
238 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate\_e}}
239 {barvinok\_enumerate\_e}}
241 The program \ai[\tt]{barvinok\_enumerate\_e} enumerates a
242 parametric projected set. It takes a single polytope in \PolyLib/
243 notation as input, followed by two lines indicating the number
244 or existential variables and the number of parameters and
245 optionally followed by a list of parameter names.
246 The syntax for the line indicating the number of existential
247 variables is the letter \verb+E+ followed by a space and the actual number.
248 For indicating the number of parameters, the letter \verb+P+ is used.
249 The following example corresponds to
250 \citeN[Example~36 on page~129]{Verdoolaege2005PhD}.
251 \begin{verbatim}
252 > cat projected
254 # k i j p cst
255 1 0 1 0 0 -1
256 1 0 -1 0 0 8
257 1 0 0 1 0 -1
258 1 0 0 -1 1 0
259 0 -1 6 9 0 -7
263 > ./barvinok_enumerate_e <projected
264 POLYHEDRON Dimension:4
265 Constraints:5 Equations:1 Rays:4 Lines:0
266 Constraints 5 6
267 Equality: [ 1 -6 -9 0 7 ]
268 Inequality: [ 0 1 0 0 -1 ]
269 Inequality: [ 0 -1 0 0 8 ]
270 Inequality: [ 0 0 1 0 -1 ]
271 Inequality: [ 0 0 -1 1 0 ]
272 Rays 4 6
273 Vertex: [ 50 8 1 1 ]/1
274 Ray: [ 0 0 0 1 ]
275 Ray: [ 9 0 1 1 ]
276 Vertex: [ 8 1 1 1 ]/1
277 exist: 2, nparam: 1
278 P -3 >= 0
279 1 >= 0
281 ( 3 * P + 10 )
282 P -1 >= 0
283 - P + 2 >= 0
285 ( 8 * P + 0 )
286 \end{verbatim}
288 Options:\\
289 \begin{tabular}{llp{0.7\textwidth}}
290 \ai[\tt]{--floor} & \ai[\tt]{-f} &
291 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
293 \ai[\tt]{--convert} & \ai[\tt]{-c} &
294 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
296 \ai[\tt]{--omega} & \ai[\tt]{-o} &
297 use \Omegalib/ as a preprocessor
299 \ai[\tt]{--pip} & \ai[\tt]{-p} &
300 \raggedright
301 call \ai[\tt]{barvinok\_enumerate\_pip} instead of \ai[\tt]{barvinok\_enumerate\_e}
302 \end{tabular}
304 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_union}}
305 {barvinok\_union}}
307 The program \ai[\tt]{barvinok\_union} enumerates a \ai{union} of
308 parametric polytopes. It takes as input the number of parametric
309 polytopes in the union, the polytopes in combined data and
310 parameter space in \PolyLib/ notation, the context in parameter space
311 in \PolyLib/ notation and optionally a list of parameter names.
313 Options:\\
314 \begin{tabular}{llp{0.7\textwidth}}
315 \ai[\tt]{--series} & \ai[\tt]{-s} &
316 compute \rgf/ instead of \psp/
317 \end{tabular}
319 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_ehrhart}}
320 {barvinok\_ehrhart}}
322 The program \ai[\tt]{barvinok\_ehrhart} computes the
323 \ai{Ehrhart quasi-polynomial} of a polytope $P$, i.e., a quasi-polynomial
324 in $n$ that evaluates to the number of integer points in the dilation
325 of $P$ by a factor $n$.
326 The input is the same as that of \ai[\tt]{barvinok\_count}, except that
327 it may be followed by the variable name.
328 The functionality is the same as running \ai[\tt]{barvinok\_enumerate}
329 (or \ai[\tt]{barvinok\_series} if the \ai[\tt]{--series} option was given)
330 on the cone over $P$ placed at $n=1$.
332 Options:\\
333 \begin{tabular}{llp{0.7\textwidth}}
334 \ai[\tt]{--floor} & \ai[\tt]{-f} &
335 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
337 \ai[\tt]{--convert} & \ai[\tt]{-c} &
338 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
340 \ai[\tt]{--series} & \ai[\tt]{-s} &
341 compute \ai{Ehrhart series} instead of \ai{Ehrhart quasi-polynomial}
342 \end{tabular}
344 \subsection{\texorpdfstring{\protect\ai[\tt]{polyhedron\_sample}}
345 {polyhedron\_sample}}
347 The program \ai[\tt]{polyhedron\_sample} takes a polytope
348 in \PolyLib/ notation and prints an integer point in the polytope
349 if there is one. The point is computed using
350 \ai[\tt]{Polyhedron\_Sample}.
352 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_scan}}
353 {polytope\_scan}}
355 The program \ai[\tt]{polytope\_scan} takes a polytope in
356 \PolyLib/ notation and prints a list of all integer points in the polytope.
357 Unless the \ai[\tt]{--direct} options is given, the order is based
358 on the \ai{reduced basis} computed with
359 \ai[\tt]{Polyhedron\_Reduced\_Basis}.
361 Options:\\
362 \begin{tabular}{llp{0.7\textwidth}}
363 \ai[\tt]{--direct} & \ai[\tt]{-d} &
364 list the points in the lexicographical order
365 \end{tabular}
367 \subsection{\texorpdfstring{\protect\ai[\tt]{lexmin}}{lexmin}}
369 The program \ai[\tt]{lexmin} implements an algorithm for performing
370 \indac{PIP} based on \rgf/s and provides an alternative for the
371 technique of \shortciteN{Feautrier88parametric}, which is based
372 on \ai{cutting plane}s \shortcite{Gomory1963}.
373 The input is the same as that of the \ai[\tt]{example} program
374 from \piplib/ \cite{Feautrier:PIP}, except that the value
375 for the ``\ai{big parameter}'' needs to be $-1$, since there is
376 no need for big parameters, and it does not read any options
377 from the input file.