evalue.c: export evalue_var
[barvinok.git] / doc / applications.tex
blobcdbb88aa30b4b6e6fba77d49dfcca98bd7502ead
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
19 \ai[\tt]{--help} & \ai[\tt]{-?} & list available options
20 \end{tabular}
22 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_count}}{barvinok\_count}}
24 The program \ai[\tt]{barvinok\_count} enumerates a
25 non-parametric polytope. It takes one polytope
26 in \PolyLib/ notation as input and prints the number
27 of integer points in the polytope.
28 The \PolyLib/ notation corresponds to the internal
29 representation of \ai[\tt]{Polyhedron}s as explained
30 in Section~\ref{a:existing}.
31 \index{input format!constraints}
32 The first line of the input contains the number of rows
33 and the number of columns in the \ai[\tt]{Constraint} matrix.
34 The rest of the input is composed of the elements of the matrix.
35 Recall that the number of columns is two more than the number
36 of variables, where the extra first columns is one or zero
37 depending on whether the constraint is an inequality ($\ge 0$)
38 or an equality ($= 0$). The next columns contain
39 the coefficients of the variables and the final column contains
40 the constant in the constraint.
41 E.g., the set
42 $S = \lb\, s \mid s \geq 0 \wedge 2 s \leq 13 \, \rb$
43 from \citeN[Example~38 on page~134]{Verdoolaege2005PhD}
44 corresponds to the following input and
45 output.
46 \begin{verbatim}
47 > cat S
48 2 3
50 1 1 0
51 1 -2 13
52 > ./barvinok_count < S
53 POLYHEDRON Dimension:1
54 Constraints:2 Equations:0 Rays:2 Lines:0
55 Constraints 2 3
56 Inequality: [ 1 0 ]
57 Inequality: [ -2 13 ]
58 Rays 2 3
59 Vertex: [ 0 ]/1
60 Vertex: [ 13 ]/2
62 \end{verbatim}
63 \index{PolyLib@{\tt PolyLib}!version 5.22.0 or newer}
64 Note that if you use \PolyLib/ version 5.22.0 or newer then the output
65 may look slightly different as the computation of the \ai[\tt]{Rays}
66 may have been postponed to a later stage.
67 The program \ai[\tt]{latte2polylib.pl} can be used to
68 convert a polytope from \ai[\tt]{LattE} \shortcite{latte1.1}
69 notation to \PolyLib/ notation.
71 \index{input format!vertices}
72 As an alternative to the constraints based input, the input polytope
73 may also be specified by its \ai[\tt]{Ray} matrix.
74 The first line of the input contains the single word \ai[\tt]{vertices}.
75 The second line contains the number of rows
76 and the number of columns in the \ai[\tt]{Ray} matrix.
77 The rest of the input is composed of the elements of the matrix.
78 Recall that the number of columns is two more than the number
79 of variables, where the extra first columns is one or zero
80 depending on whether the ray is a line or not.
81 The next columns contain
82 the numerators of the coordinates and the final column contains
83 the denominator of the vertex or $0$ for a ray.
84 E.g., the above set can also be described as
85 \begin{verbatim}
86 vertices
88 2 3
90 1 0 1
91 1 13 2
92 \end{verbatim}
94 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate}}
95 {barvinok\_enumerate}}
97 The program \ai[\tt]{barvinok\_enumerate} enumerates a
98 parametric polytope as a \psp/ or \rgf/. It takes two polytopes in \PolyLib/
99 notation as input, optionally followed by a list of parameter
100 names.
101 The two polytopes refer to arguments \verb+P+ and \verb+C+
102 of the corresponding function. (See Section~\ref{a:counting:functions}.)
103 The following example was taken by \shortciteN{Loechner1999}
104 from \shortciteN[Chapter II.2]{Loechner97phd}.
105 \begin{verbatim}
106 > cat loechner
107 # Dimension of the matrix:
108 7 7
109 # Constraints:
110 # i j k P Q cte
111 1 1 0 0 0 0 0 # 0 <= i
112 1 -1 0 0 1 0 0 # i <= P
113 1 0 1 0 0 0 0 # 0 <= j
114 1 1 -1 0 0 0 0 # j <= i
115 1 0 0 1 0 0 0 # 0 <= k
116 1 1 -1 -1 0 0 0 # k <= i-j
117 0 1 1 1 0 -1 0 # Q = i + j + k
119 # 2 parameters, no constraints.
121 > ./barvinok_enumerate < loechner
122 POLYHEDRON Dimension:5
123 Constraints:6 Equations:1 Rays:5 Lines:0
124 Constraints 6 7
125 Equality: [ 1 1 1 0 -1 0 ]
126 Inequality: [ 0 1 1 1 -1 0 ]
127 Inequality: [ 0 1 0 0 0 0 ]
128 Inequality: [ 0 0 1 0 0 0 ]
129 Inequality: [ 0 -2 -2 0 1 0 ]
130 Inequality: [ 0 0 0 0 0 1 ]
131 Rays 5 7
132 Ray: [ 1 0 1 1 2 ]
133 Ray: [ 1 1 0 1 2 ]
134 Vertex: [ 0 0 0 0 0 ]/1
135 Ray: [ 0 0 0 1 0 ]
136 Ray: [ 1 0 0 1 1 ]
137 POLYHEDRON Dimension:2
138 Constraints:1 Equations:0 Rays:3 Lines:2
139 Constraints 1 4
140 Inequality: [ 0 0 1 ]
141 Rays 3 4
142 Line: [ 1 0 ]
143 Line: [ 0 1 ]
144 Vertex: [ 0 0 ]/1
145 - P + Q >= 0
146 2P - Q >= 0
147 1 >= 0
149 ( -1/2 * P^2 + ( 1 * Q + 1/2 )
150 * P + ( -3/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 )
151 } + 1/4 )
152 * Q + ( -5/4 * {( 1/2 * Q + 0 )
153 } + 1 )
156 Q >= 0
157 P - Q -1 >= 0
158 1 >= 0
160 ( 1/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 )
161 } + 3/4 )
162 * Q + ( -5/4 * {( 1/2 * Q + 0 )
163 } + 1 )
165 \end{verbatim}
166 The output corresponds to
168 \begin{cases}
169 \makebox[0pt][l]{$-\frac 1 2 P^2 + P Q + \frac 1 2 P - \frac 3 8 Q^2
170 + \left( \frac 1 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right)
171 Q + 1
172 - \frac 5 4 \left\{ \frac 1 2 Q \right\}$} \\
174 \hbox{if $P \le Q \le 2 P$}
176 \frac 1 8 Q^2 +
177 \left( \frac 3 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right)
178 - \frac 5 4 \left\{ \frac 1 2 Q \right\}
179 \qquad
180 \qquad
181 \qquad
182 \qquad
183 \qquad
185 \hbox{if $0 \le Q \le P-1$}
187 \end{cases}
189 The following is an example of Petr Lison\u{e}k\index{Lison\u{e}k, P.}.
190 \begin{verbatim}
191 > cat petr
193 1 -1 -1 -1 1 0
194 1 1 -1 0 0 0
195 1 0 1 -1 0 0
196 1 0 0 1 0 -1
200 > ./barvinok_enumerate --series < petr
201 POLYHEDRON Dimension:4
202 Constraints:5 Equations:0 Rays:5 Lines:0
203 Constraints 5 6
204 Inequality: [ -1 -1 -1 1 0 ]
205 Inequality: [ 1 -1 0 0 0 ]
206 Inequality: [ 0 1 -1 0 0 ]
207 Inequality: [ 0 0 1 0 -1 ]
208 Inequality: [ 0 0 0 0 1 ]
209 Rays 5 6
210 Ray: [ 1 1 1 3 ]
211 Ray: [ 1 1 0 2 ]
212 Ray: [ 1 0 0 1 ]
213 Ray: [ 0 0 0 1 ]
214 Vertex: [ 1 1 1 3 ]/1
215 POLYHEDRON Dimension:1
216 Constraints:1 Equations:0 Rays:2 Lines:1
217 Constraints 1 3
218 Inequality: [ 0 1 ]
219 Rays 2 3
220 Line: [ 1 ]
221 Vertex: [ 0 ]/1
222 (n^3)/((1-n) * (1-n) * (1-n^2) * (1-n^3))
223 \end{verbatim}
225 Options:\\
226 \begin{tabular}{llp{0.7\textwidth}}
227 \ai[\tt]{--floor} & \ai[\tt]{-f} &
228 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
230 \ai[\tt]{--convert} & \ai[\tt]{-c} &
231 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
233 \ai[\tt]{--series} & \ai[\tt]{-s} &
234 compute \rgf/ instead of \psp/
236 \ai[\tt]{--explicit} & \ai[\tt]{-e} &
237 convert computed \rgf/ to a \psp/
238 \end{tabular}
240 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate\_e}}
241 {barvinok\_enumerate\_e}}
243 The program \ai[\tt]{barvinok\_enumerate\_e} enumerates a
244 parametric projected set. It takes a single polytope in \PolyLib/
245 notation as input, followed by two lines indicating the number
246 or existential variables and the number of parameters and
247 optionally followed by a list of parameter names.
248 The syntax for the line indicating the number of existential
249 variables is the letter \verb+E+ followed by a space and the actual number.
250 For indicating the number of parameters, the letter \verb+P+ is used.
251 The following example corresponds to
252 \citeN[Example~36 on page~129]{Verdoolaege2005PhD}.
253 \begin{verbatim}
254 > cat projected
256 # k i j p cst
257 1 0 1 0 0 -1
258 1 0 -1 0 0 8
259 1 0 0 1 0 -1
260 1 0 0 -1 1 0
261 0 -1 6 9 0 -7
265 > ./barvinok_enumerate_e <projected
266 POLYHEDRON Dimension:4
267 Constraints:5 Equations:1 Rays:4 Lines:0
268 Constraints 5 6
269 Equality: [ 1 -6 -9 0 7 ]
270 Inequality: [ 0 1 0 0 -1 ]
271 Inequality: [ 0 -1 0 0 8 ]
272 Inequality: [ 0 0 1 0 -1 ]
273 Inequality: [ 0 0 -1 1 0 ]
274 Rays 4 6
275 Vertex: [ 50 8 1 1 ]/1
276 Ray: [ 0 0 0 1 ]
277 Ray: [ 9 0 1 1 ]
278 Vertex: [ 8 1 1 1 ]/1
279 exist: 2, nparam: 1
280 P -3 >= 0
281 1 >= 0
283 ( 3 * P + 10 )
284 P -1 >= 0
285 - P + 2 >= 0
287 ( 8 * P + 0 )
288 \end{verbatim}
290 Options:\\
291 \begin{tabular}{llp{0.7\textwidth}}
292 \ai[\tt]{--floor} & \ai[\tt]{-f} &
293 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
295 \ai[\tt]{--convert} & \ai[\tt]{-c} &
296 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
298 \ai[\tt]{--omega} & \ai[\tt]{-o} &
299 use \Omegalib/ as a preprocessor
301 \ai[\tt]{--pip} & \ai[\tt]{-p} &
302 \raggedright
303 call \ai[\tt]{barvinok\_enumerate\_pip} instead of \ai[\tt]{barvinok\_enumerate\_e}
304 \end{tabular}
306 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_union}}
307 {barvinok\_union}}
309 The program \ai[\tt]{barvinok\_union} enumerates a \ai{union} of
310 parametric polytopes. It takes as input the number of parametric
311 polytopes in the union, the polytopes in combined data and
312 parameter space in \PolyLib/ notation, the context in parameter space
313 in \PolyLib/ notation and optionally a list of parameter names.
315 Options:\\
316 \begin{tabular}{llp{0.7\textwidth}}
317 \ai[\tt]{--series} & \ai[\tt]{-s} &
318 compute \rgf/ instead of \psp/
319 \end{tabular}
321 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_ehrhart}}
322 {barvinok\_ehrhart}}
324 \sindex{Ehrhart}{quasi-polynomial}
325 The program \ai[\tt]{barvinok\_ehrhart} computes the
326 \ai{Ehrhart quasi-polynomial} of a polytope $P$, i.e., a quasi-polynomial
327 in $n$ that evaluates to the number of integer points in the dilation
328 of $P$ by a factor $n$.
329 The input is the same as that of \ai[\tt]{barvinok\_count}, except that
330 it may be followed by the variable name.
331 The functionality is the same as running \ai[\tt]{barvinok\_enumerate}
332 on the cone over $P$ placed at $n=1$.
334 Options:\\
335 \begin{tabular}{llp{0.7\textwidth}}
336 \ai[\tt]{--floor} & \ai[\tt]{-f} &
337 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
339 \ai[\tt]{--convert} & \ai[\tt]{-c} &
340 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
342 \ai[\tt]{--series} & \ai[\tt]{-s} &
343 compute \ai{Ehrhart series} instead of \ai{Ehrhart quasi-polynomial}
344 \end{tabular}
346 \subsection{\texorpdfstring{\protect\ai[\tt]{polyhedron\_sample}}
347 {polyhedron\_sample}}
349 The program \ai[\tt]{polyhedron\_sample} takes a polytope
350 in \PolyLib/ notation and prints an integer point in the polytope
351 if there is one. The point is computed using
352 \ai[\tt]{Polyhedron\_Sample}.
354 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_scan}}
355 {polytope\_scan}}
357 The program \ai[\tt]{polytope\_scan} takes a polytope in
358 \PolyLib/ notation and prints a list of all integer points in the polytope.
359 Unless the \ai[\tt]{--direct} options is given, the order is based
360 on the \ai{reduced basis} computed with
361 \ai[\tt]{Polyhedron\_Reduced\_Basis}.
363 Options:\\
364 \begin{tabular}{llp{0.7\textwidth}}
365 \ai[\tt]{--direct} & \ai[\tt]{-d} &
366 list the points in the lexicographical order
367 \end{tabular}
369 \subsection{\texorpdfstring{\protect\ai[\tt]{lexmin}}{lexmin}}
371 The program \ai[\tt]{lexmin} implements an algorithm for performing
372 \indac{PIP} based on \rgf/s and provides an alternative for the
373 technique of \shortciteN{Feautrier88parametric}, which is based
374 on \ai{cutting plane}s \shortcite{Gomory1963}.
375 The input is the same as that of the \ai[\tt]{example} program
376 from \piplib/ \cite{Feautrier:PIP}, except that the value
377 for the ``\ai{big parameter}'' needs to be $-1$, since there is
378 no need for big parameters, and it does not read any options
379 from the input file.
381 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_summate}}
382 {barvinok\_summate}}
384 Given a piecewise quasi-polynomial,
385 the program \ai[\tt]{barvinok\_summate} computes the \ai{sum} of
386 the piecewise quasi-polynomial evaluated in all (integer) values of
387 a subset of the variables. The result is an expression in the
388 remaining variables.
390 The input format corresponds to the {\em output\/} format
391 of \ai[\tt]{barvinok\_enumerate} and \ai[\tt]{barvinok\_enumerate\_e}.
392 That is, the program expects a list of guarded quasi-polynomials.
393 Each guarded quasi-polynomial consists of a domain and a quasi-polynomial,
394 separated by an empty line.
395 The domain is specified as a list of constraints, each on a separate
396 line, consisting of an affine expression in the variables followed
397 by \verb+>= 0+.
398 Use the \ai[\tt]{--verbose} option to check that your input
399 was parsed correctly.
400 The list of guarded quasi-polynomials may be preceded by
401 a line specifying the variables over which to sum as
402 \verb+#variables+ followed by a comma separated list of variable names.
404 For example
405 \begin{verbatim}
406 > cat square_p3
407 #variables x,y
408 x -2 >= 0
409 -3x + n + 9 >= 0
410 y -4 >= 0
411 -y +5 >= 0
413 x * y
414 > ./barvinok_summate < square_p3
415 n + 3 >= 0
416 - n -1 >= 0
418 18 n >= 0
419 1 >= 0
421 ( 1/2 * n^2 + ( -3 * {( 1/3 * n + 0 )
422 } + 21/2 )
423 * n + ( 9/2 * {( 1/3 * n + 0 )
424 }^2 + -63/2 * {( 1/3 * n + 0 )
425 } + 45 )
427 \end{verbatim}
429 Options:\\
430 \begin{tabular}{llp{0.7\textwidth}}
431 \ai[\tt]{--variables} & &
432 comma separated list of variables over which to sum
434 \ai[\tt]{--verbose} & \ai[\tt]{-v} &
435 print parsed piecewise quasi-polynomial
437 \ai[\tt]{--summation} & &
438 specifies which summation method to use;
439 \ai[\tt]{barvinok} refers to the method of
440 \shortciteN[Section~4.5.4]{Verdoolaege2005PhD}, while
441 \ai[\tt]{euler} refers to the method of
442 \autoref{s:euler}
443 \end{tabular}
445 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_maximize}}
446 {barvinok\_maximize}}
448 Given a piecewise quasi-polynomial,
449 the program \ai[\tt]{barvinok\_maximize} computes an \ai{upper bound} for
450 the values attained by the piecewise quasi-polynomial
451 over all (integer) values of a subset of the variables.
452 The result is an expression in the remaining variables.
454 The input format corresponds to the {\em output\/} format
455 of \ai[\tt]{barvinok\_enumerate} and \ai[\tt]{barvinok\_enumerate\_e}.
456 That is, the program expects a list of guarded quasi-polynomials.
457 Each guarded quasi-polynomial consists of a domain and a quasi-polynomial,
458 separated by an empty line.
459 The domain is specified as a list of constraints, each on a separate
460 line, consisting of an affine expression in the variables followed
461 by \verb+>= 0+.
462 Use the \ai[\tt]{--verbose} option to check that your input
463 was parsed correctly.
464 The list of guarded quasi-polynomials may be preceded by
465 a line specifying the variables over which to compute the upper bound as
466 \verb+#variables+ followed by a comma separated list of variable names.
468 \begin{verbatim}
469 > cat devos
470 #variables V
471 U + 2V + 3 >= 0
472 - U -2V >= 0
473 - U 10 >= 0
474 U >= 0
476 ( {( 1/3 * U + ( 2/3 * V + 0 ) ) } )
477 > ./barvinok_maximize < devos
478 (1*U >= 0 && -1*U + 10 >= 0) ? ((2.0/3.0)) : 0
479 \end{verbatim}
481 Options:\\
482 \begin{tabular}{llp{0.7\textwidth}}
483 \ai[\tt]{--variables} & &
484 comma separated list of variables over which to sum
486 \ai[\tt]{--verbose} & \ai[\tt]{-v} &
487 print parsed piecewise quasi-polynomial
488 \end{tabular}