1 \section{\texorpdfstring{Applications included
2 in the
\protect\ai[\tt]{barvinok
} distribution
}
3 {Applications included in the barvinok distribution
}}
6 \index{barvinok@
{\tt barvinok
}!availability
}
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:\\
17 \ai[\tt]{--version
} &
\ai[\tt]{-V
} & print version
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.
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
50 > ./barvinok_count < S
51 POLYHEDRON Dimension:
1
52 Constraints:
2 Equations:
0 Rays:
2 Lines:
0
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
92 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok
\_enumerate}}
93 {barvinok
\_enumerate}}
95 The program
\ai[\tt]{barvinok
\_enumerate} enumerates a
96 parametric polytope. It takes two polytopes in
\PolyLib/
97 notation as input, optionally followed by a list of parameter
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
}.
105 # Dimension of the matrix:
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
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 ]
132 Vertex:
[ 0 0 0 0 0 ]/
1
135 POLYHEDRON Dimension:
2
136 Constraints:
1 Equations:
0 Rays:
3 Lines:
2
138 Inequality:
[ 0 0 1 ]
147 ( -
1/
2 * P^
2 + (
1 * Q +
1/
2 )
148 * P + ( -
3/
8 * Q^
2 + ( -
1/
2 *
{(
1/
2 * Q +
0 )
150 * Q + ( -
5/
4 *
{(
1/
2 * Q +
0 )
158 (
1/
8 * Q^
2 + ( -
1/
2 *
{(
1/
2 * Q +
0 )
160 * Q + ( -
5/
4 *
{(
1/
2 * Q +
0 )
164 The output corresponds to
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)
170 -
\frac 5 4 \left\
{ \frac 1 2 Q
\right\
}$
} \\
172 \hbox{if $P
\le Q
\le 2 P$
}
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\
}
183 \hbox{if $
0 \le Q
\le P-
1$
}
190 \ai[\tt]{--floor
} &
\ai[\tt]{-f
} &
191 convert
\ai[\tt]{fractional
}s to
\ai[\tt]{flooring
}s
193 \ai[\tt]{--convert
} &
\ai[\tt]{-c
} &
194 convert
\ai[\tt]{fractional
}s to
\ai[\tt]{periodic
}s
197 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok
\_enumerate\_e}}
198 {barvinok
\_enumerate\_e}}
200 The program
\ai[\tt]{barvinok
\_enumerate\_e} enumerates a
201 parametric projected set. It takes a single polytope in
\PolyLib/
202 notation as input, followed by two lines indicating the number
203 or existential variables and the number of parameters and
204 optionally followed by a list of parameter names.
205 The syntax for the line indicating the number of existential
206 variables is the letter
\verb+E+ followed by a space and the actual number.
207 For indicating the number of parameters, the letter
\verb+P+ is used.
208 The following example corresponds to
209 \citeN[Example~
36 on page~
129]{Verdoolaege2005PhD
}.
222 > ./barvinok_enumerate_e <projected
223 POLYHEDRON Dimension:
4
224 Constraints:
5 Equations:
1 Rays:
4 Lines:
0
226 Equality:
[ 1 -
6 -
9 0 7 ]
227 Inequality:
[ 0 1 0 0 -
1 ]
228 Inequality:
[ 0 -
1 0 0 8 ]
229 Inequality:
[ 0 0 1 0 -
1 ]
230 Inequality:
[ 0 0 -
1 1 0 ]
232 Vertex:
[ 50 8 1 1 ]/
1
235 Vertex:
[ 8 1 1 1 ]/
1
248 \begin{tabular
}{llp
{0.7\textwidth}}
249 \ai[\tt]{--floor
} &
\ai[\tt]{-f
} &
250 convert
\ai[\tt]{fractional
}s to
\ai[\tt]{flooring
}s
252 \ai[\tt]{--convert
} &
\ai[\tt]{-c
} &
253 convert
\ai[\tt]{fractional
}s to
\ai[\tt]{periodic
}s
255 \ai[\tt]{--omega
} &
\ai[\tt]{-o
} &
256 use
\Omegalib/ as a preprocessor
258 \ai[\tt]{--pip
} &
\ai[\tt]{-p
} &
260 call
\ai[\tt]{barvinok
\_enumerate\_pip} instead of
\ai[\tt]{barvinok
\_enumerate\_e}
263 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok
\_series}}
266 The program
\ai[\tt]{barvinok
\_series} enumerates a
267 parametric polytope in the form of a
\rgf/.
268 The input of this program is the same as that of
269 \ai[\tt]{barvinok
\_enumerate}, except that the input polyhedron
270 is assumed to be full-dimensional.
271 The following is an example of Petr Lison
\u{e
}k
\index{Lison
\u{e
}k, P.
}.
282 > ./barvinok_series < petr
283 POLYHEDRON Dimension:
4
284 Constraints:
5 Equations:
0 Rays:
5 Lines:
0
286 Inequality:
[ -
1 -
1 -
1 1 0 ]
287 Inequality:
[ 1 -
1 0 0 0 ]
288 Inequality:
[ 0 1 -
1 0 0 ]
289 Inequality:
[ 0 0 1 0 -
1 ]
290 Inequality:
[ 0 0 0 0 1 ]
296 Vertex:
[ 1 1 1 3 ]/
1
297 POLYHEDRON Dimension:
1
298 Constraints:
1 Equations:
0 Rays:
2 Lines:
1
304 (n^
3)/((
1-n) * (
1-n) * (
1-n^
2) * (
1-n^
3))
308 \begin{tabular
}{llp
{0.7\textwidth}}
309 \ai[\tt]{--explicit
} &
\ai[\tt]{-e
} &
310 convert computed
\rgf/ to a
\psp/
313 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok
\_union}}
316 The program
\ai[\tt]{barvinok
\_union} enumerates a
\ai{union
} of
317 parametric polytopes. It takes as input the number of parametric
318 polytopes in the union, the polytopes in combined data and
319 parameter space in
\PolyLib/ notation, the context in parameter space
320 in
\PolyLib/ notation and optionally a list of parameter names.
323 \begin{tabular
}{llp
{0.7\textwidth}}
324 \ai[\tt]{--series
} &
\ai[\tt]{-s
} &
325 compute
\rgf/ instead of
\psp/
328 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok
\_ehrhart}}
331 The program
\ai[\tt]{barvinok
\_ehrhart} computes the
332 \ai{Ehrhart quasi-polynomial
} of a polytope $P$, i.e., a quasi-polynomial
333 in $n$ that evaluates to the number of integer points in the dilation
334 of $P$ by a factor $n$.
335 The input is the same as that of
\ai[\tt]{barvinok
\_count}, except that
336 it may be followed by the variable name.
337 The functionality is the same as running
\ai[\tt]{barvinok
\_enumerate}
338 (or
\ai[\tt]{barvinok
\_series} if the
\ai[\tt]{--series
} option was given)
339 on the cone over $P$ placed at $n=
1$.
342 \begin{tabular
}{llp
{0.7\textwidth}}
343 \ai[\tt]{--floor
} &
\ai[\tt]{-f
} &
344 convert
\ai[\tt]{fractional
}s to
\ai[\tt]{flooring
}s
346 \ai[\tt]{--convert
} &
\ai[\tt]{-c
} &
347 convert
\ai[\tt]{fractional
}s to
\ai[\tt]{periodic
}s
349 \ai[\tt]{--series
} &
\ai[\tt]{-s
} &
350 compute
\ai{Ehrhart series
} instead of
\ai{Ehrhart quasi-polynomial
}
353 \subsection{\texorpdfstring{\protect\ai[\tt]{polyhedron
\_sample}}
354 {polyhedron
\_sample}}
356 The program
\ai[\tt]{polyhedron
\_sample} takes a polytope
357 in
\PolyLib/ notation and prints an integer point in the polytope
358 if there is one. The point is computed using
359 \ai[\tt]{Polyhedron
\_Sample}.
361 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope
\_scan}}
364 The program
\ai[\tt]{polytope
\_scan} takes a polytope in
365 \PolyLib/ notation and prints a list of all integer points in the polytope.
366 Unless the
\ai[\tt]{--direct
} options is given, the order is based
367 on the
\ai{reduced basis
} computed with
368 \ai[\tt]{Polyhedron
\_Reduced\_Basis}.
371 \begin{tabular
}{llp
{0.7\textwidth}}
372 \ai[\tt]{--direct
} &
\ai[\tt]{-d
} &
373 list the points in the lexicographical order
376 \subsection{\texorpdfstring{\protect\ai[\tt]{lexmin
}}{lexmin
}}
378 The program
\ai[\tt]{lexmin
} implements an algorithm for performing
379 \indac{PIP
} based on
\rgf/s and provides an alternative for the
380 technique of
\shortciteN{Feautrier88parametric
}, which is based
381 on
\ai{cutting plane
}s
\shortcite{Gomory1963
}.
382 The input is the same as that of the
\ai[\tt]{example
} program
383 from
\piplib/
\cite{Feautrier:PIP
}, except that the value
384 for the ``
\ai{big parameter
}'' needs to be $-
1$, since there is
385 no need for big parameters, and it does not read any options