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 {\tt http://freshmeat.net/projects/barvinok/.}
  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: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
  61    7
  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.
  70
  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
  87
  88 2 3
  89
  90 1 0 1
  91 1 13 2
  92 \end{verbatim}
  93
  94 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate}}
  95 {barvinok\_enumerate}}
  96
  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
 118
 119 # 2 parameters, no constraints.
 120 0 4
 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
 148
 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 )
 154  )
 155  )
 156          Q  >= 0
 157          P - Q  -1 >= 0
 158           1 >= 0
 159
 160 ( 1/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 )
 161 } + 3/4 )
 162  * Q + ( -5/4 * {( 1/2 * Q + 0 )
 163 } + 1 )
 164  )
 165 \end{verbatim}
 166 The output corresponds to
 167 $$
 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\}$} \\
 173 &
 174 \hbox{if $P \le Q \le 2 P$}
 175 \\
 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
 184 &
 185 \hbox{if $0 \le Q \le P-1$}
 186 .
 187 \end{cases}
 188 $$
 189 The following is an example of Petr Lison\u{e}k\index{Lison\u{e}k, P.}.
 190 \begin{verbatim}
 191 > cat petr
 192 4 6
 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
 197
 198 0 3
 199 n
 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}
 224
 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
 229 \\
 230 \ai[\tt]{--convert} & \ai[\tt]{-c} &
 231 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
 232 \\
 233 \ai[\tt]{--series} & \ai[\tt]{-s} &
 234 compute \rgf/ instead of \psp/
 235 \\
 236 \ai[\tt]{--explicit} & \ai[\tt]{-e} &
 237 convert computed \rgf/ to a \psp/
 238 \end{tabular}
 239
 240 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate\_e}}
 241 {barvinok\_enumerate\_e}}
 242
 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
 255 5 6
 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
 262
 263 E 2
 264 P 1
 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
 282
 283 ( 3 * P + 10 )
 284          P  -1 >= 0
 285          - P + 2 >= 0
 286
 287 ( 8 * P + 0 )
 288 \end{verbatim}
 289
 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
 294 \\
 295 \ai[\tt]{--convert} & \ai[\tt]{-c} &
 296 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
 297 \\
 298 \ai[\tt]{--omega} & \ai[\tt]{-o} &
 299 use \Omegalib/ as a preprocessor
 300 \\
 301 \ai[\tt]{--pip} & \ai[\tt]{-p} &
 302 \begin{minipage}[t]{0.7\textwidth}
 303 \raggedright
 304 call \ai[\tt]{barvinok\_enumerate\_pip} instead of \ai[\tt]{barvinok\_enumerate\_e}
 305 \end{minipage}
 306 \\
 307 \ai[\tt]{--isl} & \ai[\tt]{-i} &
 308 \raggedright
 309 call \ai[\tt]{barvinok\_enumerate\_isl} instead of \ai[\tt]{barvinok\_enumerate\_e}
 310 \end{tabular}
 311
 312 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_union}}
 313 {barvinok\_union}}
 314
 315 The program \ai[\tt]{barvinok\_union} enumerates a \ai{union} of
 316 parametric polytopes.  It takes as input the number of parametric
 317 polytopes in the union, the polytopes in combined data and
 318 parameter space in \PolyLib/ notation, the context in parameter space
 319 in \PolyLib/ notation and optionally a list of parameter names.
 320
 321 Options:\\
 322 \begin{tabular}{llp{0.7\textwidth}}
 323 \ai[\tt]{--series} & \ai[\tt]{-s} &
 324 compute \rgf/ instead of \psp/
 325 \end{tabular}
 326
 327 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_ehrhart}}
 328 {barvinok\_ehrhart}}
 329
 330 \sindex{Ehrhart}{quasi-polynomial}
 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 on the cone over $P$ placed at $n=1$.
 339
 340 Options:\\
 341 \begin{tabular}{llp{0.7\textwidth}}
 342 \ai[\tt]{--floor} & \ai[\tt]{-f} &
 343 convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s
 344 \\
 345 \ai[\tt]{--convert} & \ai[\tt]{-c} &
 346 convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s
 347 \\
 348 \ai[\tt]{--series} & \ai[\tt]{-s} &
 349 compute \ai{Ehrhart series} instead of \ai{Ehrhart quasi-polynomial}
 350 \end{tabular}
 351
 352 \subsection{\texorpdfstring{\protect\ai[\tt]{polyhedron\_sample}}
 353 {polyhedron\_sample}}
 354
 355 The program \ai[\tt]{polyhedron\_sample} takes a polytope
 356 in \PolyLib/ notation and prints an integer point in the polytope
 357 if there is one.  The point is computed using
 358 \ai[\tt]{Polyhedron\_Sample}.
 359
 360 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_scan}}
 361 {polytope\_scan}}
 362
 363 The program \ai[\tt]{polytope\_scan} takes a polytope in
 364 \PolyLib/ notation and prints a list of all integer points in the polytope.
 365 Unless the \ai[\tt]{--direct} options is given, the order is based
 366 on the \ai{reduced basis} computed with
 367 \ai[\tt]{Polyhedron\_Reduced\_Basis}.
 368
 369 Options:\\
 370 \begin{tabular}{llp{0.7\textwidth}}
 371 \ai[\tt]{--direct} & \ai[\tt]{-d} &
 372 list the points in the lexicographical order
 373 \end{tabular}
 374
 375 \subsection{\texorpdfstring{\protect\ai[\tt]{lexmin}}{lexmin}}
 376
 377 The program \ai[\tt]{lexmin} implements an algorithm for performing
 378 \indac{PIP} based on \rgf/s and provides an alternative for the
 379 technique of \shortciteN{Feautrier88parametric}, which is based
 380 on \ai{cutting plane}s \shortcite{Gomory1963}.
 381 The input is the same as that of the \ai[\tt]{example} program
 382 from \piplib/ \cite{Feautrier:PIP}, except that the value
 383 for the ``\ai{big parameter}'' needs to be $-1$, since there is
 384 no need for big parameters, and it does not read any options
 385 from the input file.
 386
 387 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_summate}}
 388 {barvinok\_summate}}
 389
 390 Given a \psp/ in \isl/ format,
 391 the program \ai[\tt]{barvinok\_summate} computes the \ai{sum} of
 392 the piecewise quasi-polynomial evaluated in all (integer) values of
 393 the variables.  The result is an expression in the parameters.
 394 Note that \ai[\tt]{barvinok\_enumerate} and \ai[\tt]{barvinok\_enumerate\_e}
 395 can produce \psp/s when given the \ai[\tt]{-I} option, but they will
 396 have only parameters and no variables.
 397
 398 For example
 399 \begin{verbatim}
 400 > cat square_p3.pwqp
 401 [n] -> { [x, y] -> x * y :
 402          n >= -9 + 3x and x >= 2 and y >= 4 and y <= 5 }
 403 > ./barvinok_summate < square_p3.pwqp
 404 [n] -> { (45 + 63/2 * [(n)/3] + 9/2 * [(n)/3]^2) : n >= -3 }
 405 \end{verbatim}
 406
 407 Options:\\
 408 \begin{tabular}{llp{0.7\textwidth}}
 409 \ai[\tt]{--summation} & &
 410 specifies which summation method to use;
 411 \ai[\tt]{box} refers to the method of
 412 \shortciteN[Section~4.5.4]{Verdoolaege2005PhD},
 413 \ai[\tt]{bernoulli} refers to the method of
 414 \autoref{s:nested:exact},
 415 \ai[\tt]{euler} refers to the method of
 416 \autoref{s:euler},
 417 and \ai[\tt]{laurent} refers to the method of
 418 \autoref{s:laurent}.
 419 \end{tabular}
 420
 421 \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_bound}}
 422 {barvinok\_bound}}
 423
 424 Given a \psp/ in \isl/ format,
 425 the program \ai[\tt]{barvinok\_bound} computes an \ai{upper bound}
 426 (or \ai{lower bound}) for
 427 the values attained by the piecewise quasi-polynomial
 428 over all (integer) values of the variables.
 429 The result is an expression in the parameters.
 430 Note that \ai[\tt]{barvinok\_enumerate} and \ai[\tt]{barvinok\_enumerate\_e}
 431 can produce \psp/s when given the \ai[\tt]{-I} option, but they will
 432 have only parameters and no variables.
 433
 434 \begin{verbatim}
 435 > cat devos.pwqp
 436 [U] -> { [V] -> ((1/3 * U + 2/3 * V) - [(U + 2V)/3]) :
 437          2V >= -3 - U and 2V <= -U and U >= 0 and U <= 10 }
 438 > ./barvinok_bound < devos.pwqp
 439 [U] -> { max(2/3) : U <= 10 and U >= 0 }
 440 \end{verbatim}
 441
 442 Options:\\
 443 \begin{tabular}{llp{0.7\textwidth}}
 444 \ai[\tt]{--lower} & &
 445 compute lower bound instead of upper bound
 446 \end{tabular}
 447
 448 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_minimize}}
 449 {polytope\_minimize}}
 450
 451 The program \ai[\tt]{polytope\_minimize} has been superseded
 452 by \isl/'s \ai[\tt]{isl\_polyhedron\_minimize}.
 453
 454 \subsection{\texorpdfstring{\protect\ai[\tt]{polyhedron\_integer\_hull}}
 455 {polyhedron\_integer\_hull}}
 456
 457 The program \ai[\tt]{polyhedron\_integer\_hull} takes a polyhedron
 458 in \PolyLib/ notation and
 459 prints its \ai{integer hull}.
 460 The integer hull is computed as explained in \autoref{s:integer:hull}.
 461
 462 \subsection{\texorpdfstring{\protect\ai[\tt]{polytope\_lattice\_width}}
 463 {polytope\_lattice\_width}}
 464
 465 The program \ai[\tt]{polytope\_lattice\_width} computes
 466 the \ai{lattice width} of a parametric polytope.
 467 The input is the same as that of \ai[\tt]{barvinok\_enumerate}.
 468 The lattice width is computed as explained
 469 in \autoref{s:width}.
 470
 471 Options:\\
 472 \begin{tabular}{llp{0.7\textwidth}}
 473 \ai[\tt]{--direction} & \ai[\tt]{-d} &
 474 print the lattice width directions
 475 \end{tabular}