doc/applications.tex

   1 \section{\texorpdfstring{Applications included
   2 in the \protect\ai[\tt]{barvinok} distribution}
   3 {Applications included in the barvinok distribution}}
   4 \label{a:usage}
   5
   6 \index{barvinok@{\tt  barvinok}!availability}
   7 {\sloppy
   8 This section describes some application programs
   9 provided by the \barvinok/ library,
  10 available from \url{https://barvinok.sourceforge.io/}.
  11 For compilation instructions we refer to the \verb+README+ file
  12 included in the distribution.
  13 }
  14
  15 Common option to all programs:\\
  16 \begin{tabular}{lll}
  17 \ai[\tt]{--version} & \ai[\tt]{-V} & print version
  18 \\
  19 \ai[\tt]{--help} & \ai[\tt]{-?} & list available options
  20 \end{tabular}
  21
  22 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_count}}{barvinok\_count}}
  23
  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
  49
  50 1 1 0
  51 1 -2 13
  52 > ./barvinok_count  < S
  53 POLYHEDRON Dimension:1
  54            Constraints:2  Equations:0  Rays:0  Lines:0
  55 Constraints 2 3
  56 Inequality: [   1    0  ]
  57 Inequality: [  -1    6  ]
  58 Rays 0 3
  59    7
  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.
  68
  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
  85
  86 2 3
  87
  88 1 0 1
  89 1 13 2
  90 \end{verbatim}
  91
  92 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate}}
  93 {barvinok\_enumerate}}
  94
  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
 116
 117 # 2 parameters, no constraints.
 118 0 4
 119 > ./barvinok_enumerate < loechner
 120          P - Q  >= 0
 121          Q  >= 0
 122           1 >= 0
 123
 124 ( 1/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 )
 125 } + 3/4 )
 126  * Q + ( -5/4 * {( 1/2 * Q + 0 )
 127 } + 1 )
 128  )
 129          2P - Q  >= 0
 130          - P + Q  -1 >= 0
 131           1 >= 0
 132
 133 ( -1/2 * P^2 + ( 1 * Q + 1/2 )
 134  * P + ( -3/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 )
 135 } + 1/4 )
 136  * Q + ( -5/4 * {( 1/2 * Q + 0 )
 137 } + 1 )
 138  )
 139  )
 140 \end{verbatim}
 141 The output corresponds to
 142 $$
 143 \begin{cases}
 144 \makebox[0pt][l]{$-\frac 1 2 P^2 + P Q + \frac 1 2 P - \frac 3 8 Q^2
 145 + \left( \frac 1 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right)
 146                 Q + 1
 147 - \frac 5 4 \left\{ \frac 1 2 Q \right\}$} \\
 148 &
 149 \hbox{if $P \le Q \le 2 P$}
 150 \\
 151 \frac 1 8 Q^2 +
 152 \left( \frac 3 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right)
 153 - \frac 5 4 \left\{ \frac 1 2 Q \right\}
 154 \qquad
 155 \qquad
 156 \qquad
 157 \qquad
 158 \qquad
 159 &
 160 \hbox{if $0 \le Q \le P-1$}
 161 .
 162 \end{cases}
 163 $$
 164 The following is an example of Petr Lison\u{e}k\index{Lison\u{e}k, P.}.
 165 \begin{verbatim}
 166 > cat petr
 167 4 6
 168 1 -1 -1 -1 1 0
 169 1 1 -1 0 0 0
 170 1 0 1 -1 0 0
 171 1 0 0 1 0 -1
 172
 173 0 3
 174 n
 175 > ./barvinok_enumerate --series < petr
 176 (n^3)/((1-n) * (1-n) * (1-n^2) * (1-n^3))
 177 \end{verbatim}
 178
 179 Options:\\
 180 \begin{tabular}{llp{0.7\textwidth}}
 181 \ai[\tt]{--floor} & \ai[\tt]{-f} &
 182 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
 183 \\
 184 \ai[\tt]{--convert} & \ai[\tt]{-c} &
 185 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
 186 \\
 187 \ai[\tt]{--series} & \ai[\tt]{-s} &
 188 compute \rgf/ instead of \psp/
 189 \\
 190 \ai[\tt]{--explicit} & \ai[\tt]{-e} &
 191 convert computed \rgf/ to a \psp/
 192 \end{tabular}
 193
 194 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate\_e}}
 195 {barvinok\_enumerate\_e}}
 196
 197 The program \ai[\tt]{barvinok\_enumerate\_e} enumerates a
 198 parametric projected set.  It takes a single polytope in \PolyLib/
 199 notation as input, followed by two lines indicating the number
 200 or existential variables and the number of parameters and
 201 optionally followed by a list of parameter names.
 202 The syntax for the line indicating the number of existential
 203 variables is the letter \verb+E+ followed by a space and the actual number.
 204 For indicating the number of parameters, the letter \verb+P+ is used.
 205 The following example corresponds to
 206 \citeN[Example~36 on page~129]{Verdoolaege2005PhD}.
 207 \begin{verbatim}
 208 > cat projected
 209 5 6
 210 #   k   i   j   p   cst
 211 1   0   1   0   0   -1
 212 1   0   -1  0   0   8
 213 1   0   0   1   0   -1
 214 1   0   0   -1  1   0
 215 0   -1  6   9   0   -7
 216
 217 E 2
 218 P 1
 219 > ./barvinok_enumerate_e <projected
 220          P  -3 >= 0
 221           1 >= 0
 222
 223 ( 3 * P + 10 )
 224          P  -1 >= 0
 225          - P + 2 >= 0
 226
 227 ( 8 * P + 0 )
 228 \end{verbatim}
 229
 230 Options:\\
 231 \begin{tabular}{llp{0.7\textwidth}}
 232 \ai[\tt]{--floor} & \ai[\tt]{-f} &
 233 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
 234 \\
 235 \ai[\tt]{--convert} & \ai[\tt]{-c} &
 236 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
 237 \\
 238 \ai[\tt]{--isl} & \ai[\tt]{-i} &
 239 \raggedright
 240 call \ai[\tt]{barvinok\_enumerate\_isl} instead of \ai[\tt]{barvinok\_enumerate\_e}
 241 \end{tabular}
 242
 243 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_union}}
 244 {barvinok\_union}}
 245
 246 The program \ai[\tt]{barvinok\_union} enumerates a \ai{union} of
 247 parametric polytopes.  It takes as input the number of parametric
 248 polytopes in the union, the polytopes in combined data and
 249 parameter space in \PolyLib/ notation, the context in parameter space
 250 in \PolyLib/ notation and optionally a list of parameter names.
 251
 252 Options:\\
 253 \begin{tabular}{llp{0.7\textwidth}}
 254 \ai[\tt]{--series} & \ai[\tt]{-s} &
 255 compute \rgf/ instead of \psp/
 256 \end{tabular}
 257
 258 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_ehrhart}}
 259 {barvinok\_ehrhart}}
 260
 261 \sindex{Ehrhart}{quasi-polynomial}
 262 The program \ai[\tt]{barvinok\_ehrhart} computes the
 263 \ai{Ehrhart quasi-polynomial} of a polytope $P$, i.e., a quasi-polynomial
 264 in $n$ that evaluates to the number of integer points in the dilation
 265 of $P$ by a factor $n$.
 266 The input is the same as that of \ai[\tt]{barvinok\_count}, except that
 267 it may be followed by the variable name.
 268 The functionality is the same as running \ai[\tt]{barvinok\_enumerate}
 269 on the cone over $P$ placed at $n=1$.
 270
 271 Options:\\
 272 \begin{tabular}{llp{0.7\textwidth}}
 273 \ai[\tt]{--floor} & \ai[\tt]{-f} &
 274 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
 275 \\
 276 \ai[\tt]{--convert} & \ai[\tt]{-c} &
 277 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
 278 \\
 279 \ai[\tt]{--series} & \ai[\tt]{-s} &
 280 compute \ai{Ehrhart series} instead of \ai{Ehrhart quasi-polynomial}
 281 \end{tabular}
 282
 283 \subsection{\texorpdfstring{\protect\ai[\tt]{polyhedron\_sample}}
 284 {polyhedron\_sample}}
 285
 286 The program \ai[\tt]{polyhedron\_sample} takes a polytope
 287 in \PolyLib/ notation and prints an integer point in the polytope
 288 if there is one.  The point is computed using
 289 \ai[\tt]{Polyhedron\_Sample}.
 290
 291 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_scan}}
 292 {polytope\_scan}}
 293
 294 The program \ai[\tt]{polytope\_scan} takes a polytope in
 295 \PolyLib/ notation and prints a list of all integer points in the polytope.
 296 Unless the \ai[\tt]{--direct} options is given, the order is based
 297 on the \ai{reduced basis} computed with
 298 \ai[\tt]{Polyhedron\_Reduced\_Basis}.
 299
 300 Options:\\
 301 \begin{tabular}{llp{0.7\textwidth}}
 302 \ai[\tt]{--direct} & \ai[\tt]{-d} &
 303 list the points in the lexicographical order
 304 \end{tabular}
 305
 306 \subsection{\texorpdfstring{\protect\ai[\tt]{lexmin}}{lexmin}}
 307
 308 The program \ai[\tt]{lexmin} implements an algorithm for performing
 309 \indac{PIP} based on \rgf/s and provides an alternative for the
 310 technique of \shortciteN{Feautrier88parametric}, which is based
 311 on \ai{cutting plane}s \shortcite{Gomory1963}.
 312 The input is the same as that of the \ai[\tt]{example} program
 313 from \piplib/ \cite{Feautrier:PIP}, except that the value
 314 for the ``\ai{big parameter}'' needs to be $-1$, since there is
 315 no need for big parameters, and it does not read any options
 316 from the input file.
 317
 318 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_summate}}
 319 {barvinok\_summate}}
 320
 321 Given a \psp/ in \isl/ format,
 322 the program \ai[\tt]{barvinok\_summate} computes the \ai{sum} of
 323 the piecewise quasi-polynomial evaluated in all (integer) values of
 324 the variables.  The result is an expression in the parameters.
 325 Note that \ai[\tt]{barvinok\_enumerate} and \ai[\tt]{barvinok\_enumerate\_e}
 326 can produce \psp/s when given the \ai[\tt]{-I} option, but they will
 327 have only parameters and no variables.
 328
 329 For example
 330 \begin{verbatim}
 331 > cat square_p3.pwqp
 332 [n] -> { [x, y] -> x * y :
 333          n >= -9 + 3x and x >= 2 and y >= 4 and y <= 5 }
 334 > ./barvinok_summate < square_p3.pwqp
 335 [n] -> { (45 + 63/2 * floor((n)/3) + 9/2 * floor((n)/3)^2) : n >= -3 }
 336 \end{verbatim}
 337
 338 Options:\\
 339 \begin{tabular}{llp{0.7\textwidth}}
 340 \ai[\tt]{--summation} & &
 341 specifies which summation method to use;
 342 \ai[\tt]{box} refers to the method of
 343 \shortciteN[Section~4.5.4]{Verdoolaege2005PhD},
 344 \ai[\tt]{bernoulli} refers to the method of
 345 \autoref{s:nested:exact},
 346 \ai[\tt]{euler} refers to the method of
 347 \autoref{s:euler},
 348 and \ai[\tt]{laurent} refers to the method of
 349 \autoref{s:laurent}.
 350 \end{tabular}
 351
 352 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_bound}}
 353 {barvinok\_bound}}
 354
 355 Given a \psp/ in \isl/ format,
 356 the program \ai[\tt]{barvinok\_bound} computes an \ai{upper bound}
 357 (or \ai{lower bound}) for
 358 the values attained by the piecewise quasi-polynomial
 359 over all (integer) values of the variables.
 360 The result is an expression in the parameters.
 361 Note that \ai[\tt]{barvinok\_enumerate} and \ai[\tt]{barvinok\_enumerate\_e}
 362 can produce \psp/s when given the \ai[\tt]{-I} option, but they will
 363 have only parameters and no variables.
 364
 365 \begin{verbatim}
 366 > cat devos.pwqp
 367 [U] -> { [V] -> ((1/3 * U + 2/3 * V) - [(U + 2V)/3]) :
 368          2V >= -3 - U and 2V <= -U and U >= 0 and U <= 10 }
 369 > ./barvinok_bound < devos.pwqp
 370 [U] -> { max(2/3) : 0 <= U <= 10 }
 371 \end{verbatim}
 372
 373 Options:\\
 374 \begin{tabular}{llp{0.7\textwidth}}
 375 \ai[\tt]{--lower} & &
 376 compute lower bound instead of upper bound
 377 \end{tabular}
 378
 379 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_minimize}}
 380 {polytope\_minimize}}
 381
 382 The program \ai[\tt]{polytope\_minimize} has been superseded
 383 by \isl/'s \ai[\tt]{isl\_polyhedron\_minimize}.
 384
 385 \subsection{\texorpdfstring{\protect\ai[\tt]{polyhedron\_integer\_hull}}
 386 {polyhedron\_integer\_hull}}
 387
 388 The program \ai[\tt]{polyhedron\_integer\_hull} takes a polyhedron
 389 in \PolyLib/ notation and
 390 prints its \ai{integer hull}.
 391 The integer hull is computed as explained in \autoref{s:integer:hull}.
 392
 393 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_lattice\_width}}
 394 {polytope\_lattice\_width}}
 395
 396 The program \ai[\tt]{polytope\_lattice\_width} computes
 397 the \ai{lattice width} of a parametric polytope.
 398 The input is the same as that of \ai[\tt]{barvinok\_enumerate}.
 399 The lattice width is computed as explained
 400 in \autoref{s:width}.
 401
 402 Options:\\
 403 \begin{tabular}{llp{0.7\textwidth}}
 404 \ai[\tt]{--direction} & \ai[\tt]{-d} &
 405 print the lattice width directions
 406 \end{tabular}