doc/Internal.tex

   1 \section{\protect\PolyLib/ interface of the \protect\ai[\tt]{barvinok} library}
   2
   3 Our \barvinok/ library is built on top of \PolyLib/
   4 \shortcite{Wilde1993,Loechner1999}.
   5 In particular, it reuses the implementations
   6 of the algorithm of
   7 \shortciteN{Loechner97parameterized}
   8 for computing parametric vertices
   9 and the algorithm of
  10 \shortciteN{Clauss1998parametric}
  11 for computing chamber decompositions.
  12 Initially, our library was meant to be a replacement
  13 for the algorithm of \shortciteN{Clauss1998parametric},
  14 also implemented in \PolyLib/, for computing quasi-polynomials.
  15 To ease the transition of application programs we
  16 tried to reuse the existing data structures as much as possible.
  17
  18 \subsection{Existing Data Structures}
  19 \label{a:existing}
  20
  21 Inside \PolyLib/ integer values are represented by the
  22 \ai[\tt]{Value} data type.
  23 Depending on a configure option, the data type may
  24 either by a 32-bit integer, a 64-bit integer
  25 or an arbitrary precision integer using \ai[\tt]{GMP}.
  26 The \barvinok/ library requires that \PolyLib/ is compiled
  27 with support for arbitrary precision integers.
  28
  29 The basic structure for representing (unions of) polyhedra is a
  30 \ai[\tt]{Polyhedron}.
  31 \begin{verbatim}
  32 typedef struct polyhedron {
  33   unsigned Dimension, NbConstraints, NbRays, NbEq, NbBid;
  34   Value **Constraint;
  35   Value **Ray;
  36   Value *p_Init;
  37   int p_Init_size;
  38   struct polyhedron *next;
  39 } Polyhedron;
  40 \end{verbatim}
  41 The attribute \ai[\tt]{Dimension} is the dimension
  42 of the ambient space, i.e., the number of variables.
  43 The attributes \ai[\tt]{Constraint}
  44 and \ai[\tt]{Ray} point to two-dimensional arrays
  45 of constraints and generators, respectively.
  46 The number of rows is stored in
  47 \ai[\tt]{NbConstraints} and
  48 \ai[\tt]{NbRays}, respectively.
  49 The number of columns in both arrays is equal
  50 to \verb!1+Dimension+1!.
  51 The first column of \ai[\tt]{Constraint} is either
  52 $0$ or $1$ depending on whether the constraint
  53 is an equality ($0$) or an inequality ($1$).
  54 The number of equalities is stored in \ai[\tt]{NbEq}.
  55 If the constraint is $\sp a x + c \ge 0$, then
  56 the next columns contain the coefficients $a_i$
  57 and the final column contains the constant $c$.
  58 The first column of \ai[\tt]{Ray} is either
  59 $0$ or $1$ depending on whether the generator
  60 is a line ($0$) or a vertex or ray ($1$).
  61 The number of lines is stored in \ai[\tt]{NbBid}.
  62 Let $d$ be the \ac{lcm} of the denominators of the coordinates
  63 of a vertex $\vec v$, then the next columns contain
  64 $d v_i$ and the final column contains $d$.
  65 For a ray, the final column contains $0$.
  66 The field \ai[\tt]{next} points to the next polyhedron in
  67 the union of polyhedra.
  68 It is \verb+0+ if this is the last (or only) polyhedron in the union.
  69 For more information on this structure, we refer to \shortciteN{Wilde1993}.
  70
  71 Quasi-polynomials are represented using the
  72 \ai[\tt]{evalue} and \ai[\tt]{enode} structures.
  73 \begin{verbatim}
  74 typedef enum { polynomial, periodic, evector } enode_type;
  75
  76 typedef struct _evalue {
  77   Value d;              /* denominator */
  78   union {
  79     Value n;            /* numerator (if denominator != 0) */
  80     struct _enode *p;   /* pointer   (if denominator == 0) */
  81   } x;
  82 } evalue;
  83
  84 typedef struct _enode {
  85   enode_type type;      /* polynomial or periodic or evector */
  86   int size;             /* number of attached pointers */
  87   int pos;              /* parameter position */
  88   evalue arr[1];        /* array of rational/pointer */
  89 } enode;
  90 \end{verbatim}
  91 If the field \ai[\tt]{d} of an \ai[\tt]{evalue} is zero, then
  92 the \ai[\tt]{evalue} is a placeholder for a pointer to
  93 an \ai[\tt]{enode}, stored in \ai[\tt]{x.p}.
  94 Otherwise, the \ai[\tt]{evalue} is a rational number with
  95 numerator \ai[\tt]{x.n} and denominator \ai[\tt]{d}.
  96 An \ai[\tt]{enode} is either a \ai[\tt]{polynomial}
  97 or a \ai[\tt]{periodic}, depending on the value
  98 of \ai[\tt]{type}.
  99 The length of the array \ai[\tt]{arr} is stored in \ai[\tt]{size}.
 100 For a \ai[\tt]{polynomial}, \ai[\tt]{arr} contains the coefficients.
 101 For a \ai[\tt]{periodic}, it contains the values for the different
 102 residue classes modulo the parameter indicated by \ai[\tt]{pos}.
 103 For a polynomial, \ai[\tt]{pos} refers to the variable
 104 of the polynomial.
 105 The value of \ai[\tt]{pos} is \verb+1+ for the first parameter.
 106 That is, if the value of \ai[\tt]{pos} is \verb+1+ and the first
 107 parameter is $p$, and if the length of the array is $l$,
 108 then in case it is a polynomial, the
 109  \ai[\tt]{enode} represents
 110 $$
 111 \verb+arr[0]+ + \verb+arr[1]+ p + \verb+arr[2]+ p^2 + \cdots +
 112 \verb+arr[l-1]+ p^{l-1}
 113 .
 114 $$
 115 If it is a periodic, then it represents
 116 $$
 117 \left[
 118 \verb+arr[0]+, \verb+arr[1]+,  \verb+arr[2]+, \ldots,
 119 \verb+arr[l-1]+
 120 \right]_p
 121 .
 122 $$
 123 Note that the elements of a \ai[\tt]{periodic} may themselves
 124 be other \ai[\tt]{periodic}s or even \ai[\tt]{polynomial}s.
 125 In our library, we only allow the elements of a  \ai[\tt]{periodic}
 126 to be other \ai[\tt]{periodic}s or rational numbers.
 127 The chambers and their corresponding quasi-polynomial are
 128 stored in \ai[\tt]{Enumeration} structures.
 129 \begin{verbatim}
 130 typedef struct _enumeration {
 131   Polyhedron *ValidityDomain; /* constraints on the parameters */
 132   evalue EP;                  /* dimension = combined space    */
 133   struct _enumeration *next;  /* Ehrhart Polynomial,
 134                                  corresponding to parameter
 135                                  values inside the domain
 136                                  ValidityDomain above          */
 137 } Enumeration;
 138 \end{verbatim}
 139 For more information on these structures, we refer to \shortciteN{Loechner1999}.
 140
 141 \begin{example}
 142 Figure~\ref{f:Loechner} is a skillful reconstruction
 143 of Figure~2 from \shortciteN{Loechner1999}.
 144 It shows the contents of the \ai[\tt]{enode} structures
 145 representing the quasi-polynomial
 146 $
 147 [1,2]_p p^2 + 3 p + \frac 5 2
 148 $.
 149
 150 \begin{figure}
 151 \begin{xy}
 152 \POS(0,0)*!UL{\hbox{
 153 \tt
 154 \begin{tabular}{|c|c|c|}
 155 \hline
 156 \multicolumn{2}{|c|}{type} & polynomial \\
 157 \hline
 158 \multicolumn{2}{|c|}{size} & 3 \\
 159 \hline
 160 \multicolumn{2}{|c|}{pos} & 1 \\
 161 \hline
 162 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 2 \\
 163 \cline{2-3}
 164        & x.n & 5 \\
 165 \hline
 166 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\
 167 \cline{2-3}
 168        & x.n & 3 \\
 169 \hline
 170 \smash{\lower 6.25pt\hbox{arr[2]}} & d & 0 \\
 171 \cline{2-3}
 172        & x.p &   \\
 173 \hline
 174 \end{tabular}
 175 }
 176 }="box1"
 177 +DR*!DR\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial}\hskip 1.5\tabcolsep}+C="a"
 178 \POS(60,-15)*!UL{\hbox{
 179 \tt
 180 \begin{tabular}{|c|c|c|}
 181 \hline
 182 \multicolumn{2}{|c|}{type} & periodic \\
 183 \hline
 184 \multicolumn{2}{|c|}{size} & 2 \\
 185 \hline
 186 \multicolumn{2}{|c|}{pos} & 1 \\
 187 \hline
 188 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 1 \\
 189 \cline{2-3}
 190        & x.n & 1 \\
 191 \hline
 192 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\
 193 \cline{2-3}
 194        & x.n & 2 \\
 195 \hline
 196 \end{tabular}
 197 }
 198 }="box2"
 199 +UL+<0.5\tabcolsep,0pt>*!UL\hbox{\strut}+CL="b"
 200 \POS"a"\ar@(r,l) "b"
 201 \POS"box1"+UC*++!D\hbox{\tt enode}
 202 \POS"box2"+UC*++!D\hbox{\tt enode}
 203 \end{xy}
 204 \caption{The quasi-polynomial $[1,2]_p p^2 + 3 p + \frac 5 2$.}
 205 \label{f:Loechner}
 206 \end{figure}
 207 \end{example}
 208
 209 \subsection{Options}
 210 \label{a:options}
 211
 212 The \ai[\tt]{barvinok\_options} structure contains various
 213 options that influence the behavior of the library.
 214
 215 \begin{verbatim}
 216 struct barvinok_options {
 217     struct barvinok_stats   *stats;
 218
 219     /* PolyLib options */
 220     unsigned    MaxRays;
 221
 222     /* NTL options */
 223                 /* LLL reduction parameter delta=LLL_a/LLL_b */
 224     long        LLL_a;
 225     long        LLL_b;
 226
 227     /* barvinok options */
 228     #define     BV_SPECIALIZATION_BF            2
 229     #define     BV_SPECIALIZATION_DF            1
 230     #define     BV_SPECIALIZATION_RANDOM        0
 231     #define     BV_SPECIALIZATION_TODD          3
 232     int         incremental_specialization;
 233
 234     unsigned long           max_index;
 235     int                     primal;
 236     int                     lookup_table;
 237     int                     count_sample_infinite;
 238
 239     int                     try_Delaunay_triangulation;
 240
 241     #define     BV_APPROX_SIGN_NONE     0
 242     #define     BV_APPROX_SIGN_APPROX   1
 243     #define     BV_APPROX_SIGN_LOWER    2
 244     #define     BV_APPROX_SIGN_UPPER    3
 245     int                     polynomial_approximation;
 246     #define     BV_APPROX_NONE          0
 247     #define     BV_APPROX_DROP          1
 248     #define     BV_APPROX_SCALE         2
 249     #define     BV_APPROX_VOLUME        3
 250     #define     BV_APPROX_BERNOULLI     4
 251     int                     approximation_method;
 252     #define     BV_APPROX_SCALE_FAST    (1 << 0)
 253     #define     BV_APPROX_SCALE_NARROW  (1 << 1)
 254     #define     BV_APPROX_SCALE_NARROW2 (1 << 2)
 255     #define     BV_APPROX_SCALE_CHAMBER (1 << 3)
 256     int                     scale_flags;
 257     #define     BV_VOL_LIFT             0
 258     #define     BV_VOL_VERTEX           1
 259     #define     BV_VOL_BARYCENTER       2
 260     int                     volume_triangulate;
 261
 262     /* basis reduction options */
 263     #define     BV_GBR_NONE     0
 264     #define     BV_GBR_GLPK     1
 265     #define     BV_GBR_CDD      2
 266     int         gbr_lp_solver;
 267
 268     #define     BV_LP_POLYLIB           0
 269     #define     BV_LP_GLPK              1
 270     #define     BV_LP_CDD               2
 271     #define     BV_LP_CDDF              3
 272     #define     BV_LP_PIP               4
 273     int         lp_solver;
 274
 275     #define     BV_HULL_GBR             0
 276     #define     BV_HULL_HILBERT         1
 277     int         integer_hull;
 278 };
 279
 280 struct barvinok_options *barvinok_options_new_with_defaults();
 281 \end{verbatim}
 282
 283 The function \ai[\tt]{barvinok\_options\_new\_with\_defaults}
 284 can be used to create a \ai[\tt]{barvinok\_options} structure
 285 with default values.
 286
 287 \begin{itemize}
 288 \item \PolyLib/ options
 289
 290 \begin{itemize}
 291
 292 \item \ai[\tt]{MaxRays}
 293
 294 The value of \ai[\tt]{MaxRays} is passed to various \PolyLib/
 295 functions and defines the
 296 maximum size of a table used in the \ai{double description} computation
 297 in the \PolyLib/ function \ai[\tt]{Chernikova}.
 298 In earlier versions of \PolyLib/,
 299 this parameter had to be conservatively set
 300 to a high number to ensure successful operation,
 301 resulting in significant memory overhead.
 302 Our change to allow this table to grow
 303 dynamically is available in recent versions of \PolyLib/.
 304 In these versions, the value no longer indicates the maximal
 305 table size, but rather the size of the initial allocation.
 306 This value may be set to \verb+0+ or left as set
 307 by \ai[\tt]{barvinok\_options\_new\_with\_defaults}.
 308
 309 \end{itemize}
 310
 311 \item \ai[\tt]{NTL} options
 312
 313 \begin{itemize}
 314
 315 \item \ai[\tt]{LLL\_a}
 316 \item \ai[\tt]{LLL\_b}
 317
 318 The values used for the \ai{reduction parameter}
 319 in the call to \ai[\tt]{NTL}'s implementation of \indac{LLL}.
 320
 321 \end{itemize}
 322
 323 \item \ai[\tt]{barvinok} specific options
 324
 325 \begin{itemize}
 326
 327 \item \ai[\tt]{incremental\_specialization}
 328
 329 Selects the \ai{specialization} algorithm to be used.
 330 If set to {\tt 0} then a direct specialization is performed
 331 using a random vector.
 332 Value {\tt 1} selects a depth first incremental specialization,
 333 while value {\tt 2} selects a breadth first incremental specialization.
 334 The default is selected by the \ai[\tt]{--enable-incremental}
 335 \ai[\tt]{configure} option.
 336 For more information we refer to~\citeN[Section~4.4.3]{Verdoolaege2005PhD}.
 337
 338 \end{itemize}
 339
 340 \end{itemize}
 341
 342 \subsection{Data Structures for Quasi-polynomials}
 343 \label{a:data}
 344
 345 Internally, we do not represent our \ai{quasi-polynomial}s
 346 as step-polynomials, but instead as polynomials of
 347 fractional parts of degree-$1$ polynomials.
 348 However, we also allow our quasi-polynomials to be represented
 349 as polynomials with periodic numbers for coefficients,
 350 similarly to \shortciteN{Loechner1999}.
 351 By default, the current version of \barvinok/ uses
 352 \ai[\tt]{fractional}s, but this can be changed through
 353 the \ai[\tt]{--disable-fractional} configure option.
 354 When this option is specified, the periodic numbers
 355 are represented as
 356 an explicit enumeration using the \ai[\tt]{periodic} type.
 357 A quasi-polynomial based on fractional
 358 parts can also be converted to an actual step-polynomial
 359 using \ai[\tt]{evalue\_frac2floor}, but this is not fully
 360 supported yet.
 361
 362 For reasons of compatibility,%
 363 \footnote{Also known as laziness.}
 364 we shoehorned our representations for piecewise quasi-polynomials
 365 into the existing data structures.
 366 To this effect, we introduced four new types,
 367 \ai[\tt]{fractional}, \ai[\tt]{relation},
 368 \ai[\tt]{partition} and \ai[\tt]{flooring}.
 369 \begin{verbatim}
 370 typedef enum { polynomial, periodic, evector, fractional,
 371                relation, partition, flooring } enode_type;
 372 \end{verbatim}
 373 The field \ai[\tt]{pos} is not used in most of these
 374 additional types and is therefore set to \verb+-1+.
 375
 376 The types \ai[\tt]{fractional} and \ai[\tt]{flooring}
 377 represent polynomial expressions in a fractional part or a floor respectively.
 378 The generator is stored in \verb+arr[0]+, while the
 379 coefficients are stored in the remaining array elements.
 380 That is, an \ai[\tt]{enode} of type \ai[\tt]{fractional}
 381 represents
 382 $$
 383 \verb+arr[1]+ + \verb+arr[2]+ \{\verb+arr[0]+\} +
 384 \verb+arr[3]+ \{\verb+arr[0]+\}^2 + \cdots +
 385 \verb+arr[l-1]+ \{\verb+arr[0]+\}^{l-2}
 386 .
 387 $$
 388 An \ai[\tt]{enode} of type \ai[\tt]{flooring}
 389 represents
 390 $$
 391 \verb+arr[1]+ + \verb+arr[2]+ \lfloor\verb+arr[0]+\rfloor +
 392 \verb+arr[3]+ \lfloor\verb+arr[0]+\rfloor^2 + \cdots +
 393 \verb+arr[l-1]+ \lfloor\verb+arr[0]+\rfloor^{l-2}
 394 .
 395 $$
 396
 397 \begin{example}
 398 The internal representation of the quasi-polynomial
 399 $$\left(1+2 \left\{\frac p 2\right\}\right) p^2 + 3 p + \frac 5 2$$
 400 is shown in Figure~\ref{f:fractional}.
 401
 402 \begin{figure}
 403 \begin{xy}
 404 \POS(0,0)*!UL{\hbox{
 405 \tt
 406 \begin{tabular}{|c|c|c|}
 407 \hline
 408 \multicolumn{2}{|c|}{type} & polynomial \\
 409 \hline
 410 \multicolumn{2}{|c|}{size} & 3 \\
 411 \hline
 412 \multicolumn{2}{|c|}{pos} & 1 \\
 413 \hline
 414 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 2 \\
 415 \cline{2-3}
 416        & x.n & 5 \\
 417 \hline
 418 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\
 419 \cline{2-3}
 420        & x.n & 3 \\
 421 \hline
 422 \smash{\lower 6.25pt\hbox{arr[2]}} & d & 0 \\
 423 \cline{2-3}
 424        & x.p &   \\
 425 \hline
 426 \end{tabular}
 427 }
 428 }="box1"
 429 +DR*!DR\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial}\hskip 1.5\tabcolsep}+C="a"
 430 \POS(60,0)*!UL{\hbox{
 431 \tt
 432 \begin{tabular}{|c|c|c|}
 433 \hline
 434 \multicolumn{2}{|c|}{type} & fractional \\
 435 \hline
 436 \multicolumn{2}{|c|}{size} & 3 \\
 437 \hline
 438 \multicolumn{2}{|c|}{pos} & -1 \\
 439 \hline
 440 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 0 \\
 441 \cline{2-3}
 442        & x.p &   \\
 443 \hline
 444 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\
 445 \cline{2-3}
 446        & x.n & 1 \\
 447 \hline
 448 \smash{\lower 6.25pt\hbox{arr[2]}} & d & 1 \\
 449 \cline{2-3}
 450        & x.n & 2 \\
 451 \hline
 452 \end{tabular}
 453 }
 454 }="box2"
 455 +UL+<0.5\tabcolsep,0pt>*!UL\hbox{\strut}+CL="b"
 456 \POS"a"\ar@(r,l) "b"
 457 \POS"box2"+UR*!UR{\hbox{
 458 \tt
 459 \begin{tabular}{|c|}
 460 \hline
 461  fractional \\
 462 \hline
 463  3 \\
 464 \hline
 465  -1 \\
 466 \hline
 467  0 \\
 468 \hline
 469 \end{tabular}
 470 }
 471 }+CD*!U{\strut}+C="c"
 472 \POS(60,-50)*!UL{\hbox{
 473 \tt
 474 \begin{tabular}{|c|c|c|}
 475 \hline
 476 \multicolumn{2}{|c|}{type} & polynomial \\
 477 \hline
 478 \multicolumn{2}{|c|}{size} & 2 \\
 479 \hline
 480 \multicolumn{2}{|c|}{pos} & 1 \\
 481 \hline
 482 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 1 \\
 483 \cline{2-3}
 484        & x.n & 0 \\
 485 \hline
 486 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 2 \\
 487 \cline{2-3}
 488        & x.n & 1 \\
 489 \hline
 490 \end{tabular}
 491 }
 492 }="box3"
 493 +UR-<0.8\tabcolsep,0pt>*!UR\hbox{\strut}+CR="d"
 494 \POS"c"\ar@(r,r) "d"
 495 \POS"box1"+UC*++!D\hbox{\tt enode}
 496 \POS"box2"+UC*++!D\hbox{\tt enode}
 497 \POS"box3"+UC*++!D\hbox{\tt enode}
 498 \end{xy}
 499 \caption{The quasi-polynomial
 500 $\left(1+2 \left\{\frac p 2\right\}\right) p^2 + 3 p + \frac 5 2$.}
 501 \label{f:fractional}
 502 \end{figure}
 503
 504 \end{example}
 505
 506 The \ai[\tt]{relation} type is used to represent \ai{stride}s.
 507 In particular, if the value of \ai[\tt]{size} is 2, then
 508 the value of a \ai[\tt]{relation} is (in pseudo-code):
 509 \begin{verbatim}
 510 (value(arr[0]) == 0) ? value(arr[1]) : 0
 511 \end{verbatim}
 512 If the size is 3, then the value is:
 513 \begin{verbatim}
 514 (value(arr[0]) == 0) ? value(arr[1]) : value(arr[2])
 515 \end{verbatim}
 516 The type of \verb+arr[0]+ is typically \ai[\tt]{fractional}.
 517
 518 Finally, the \ai[\tt]{partition} type is used to
 519 represent piecewise quasi-polynomials.
 520 We prefer to encode this information inside \ai[\tt]{evalue}s
 521 themselves
 522 rather than using \ai[\tt]{Enumeration}s since we want
 523 to perform the same kinds of operations on both quasi-polynomials
 524 and piecewise quasi-polynomials.
 525 An \ai[\tt]{enode} of type \ai[\tt]{partition} may not be nested
 526 inside another \ai[\tt]{enode}.
 527 The size of the array is twice the number of ``chambers''.
 528 Pointers to chambers are stored in the even slots,
 529 whereas pointer to the associated quasi-polynomials
 530 are stored in the odd slots.
 531 To be able to store pointers to chambers, the
 532 definition of \ai[\tt]{evalue} was changed as follows.
 533 \begin{verbatim}
 534 typedef struct _evalue {
 535   Value d;              /* denominator */
 536   union {
 537     Value n;            /* numerator (if denominator > 0) */
 538     struct _enode *p;   /* pointer   (if denominator == 0) */
 539     Polyhedron *D;      /* domain    (if denominator == -1) */
 540   } x;
 541 } evalue;
 542 \end{verbatim}
 543 Note that we allow a ``chamber'' to be a union of polyhedra
 544 as discussed in \citeN[Section~4.5.1]{Verdoolaege2005PhD}.
 545 Chambers with extra variables, i.e., those of
 546 \citeN[Section~4.6.5]{Verdoolaege2005PhD},
 547 are only partially supported.
 548 The field \ai[\tt]{pos} is set to the actual dimension,
 549 i.e., the number of parameters.
 550
 551 \subsection{Operations on Quasi-polynomials}
 552 \label{a:operations}
 553
 554 In this section we discuss some of the more important
 555 operations on \ai[\tt]{evalue}s provided by the
 556 \barvinok/ library.
 557 Some of these operations are extensions
 558 of the functions from \PolyLib/ with the same name.
 559
 560 Most of these operation are also provided by \isl/ on
 561 \ai[\tt]{isl\_pw\_qpolynomial}s, which are set to replace
 562 \ai[\tt]{evalue}s.  Use \ai[\tt]{isl\_pw\_qpolynomial\_from\_evalue} to convert
 563 from \ai[\tt]{evalue}s to \ai[\tt]{isl\_pw\_qpolynomial}s.
 564 \begin{verbatim}
 565 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_evalue(
 566         __isl_take isl_dim *dim, const evalue *e);
 567 \end{verbatim}
 568
 569 \begin{verbatim}
 570 void eadd(const evalue *e1,evalue *res);
 571 void emul(const evalue *e1, evalue *res);
 572 \end{verbatim}
 573 The functions \ai[\tt]{eadd} and \ai[\tt]{emul} takes
 574 two (pointers to) \ai[\tt]{evalue}s \verb+e1+ and \verb+res+
 575 and computes their sum and product respectively.
 576 The result is stored in \verb+res+, overwriting (and deallocating)
 577 the original value of \verb+res+.
 578 It is an error if exactly one of
 579 the arguments of \ai[\tt]{eadd} is of type \ai[\tt]{partition}
 580 (unless the other argument is \verb+0+).
 581 The addition and multiplication operations are described
 582 in \citeN[Section~4.5.1]{Verdoolaege2005PhD}
 583 and~\citeN[Section~4.5.2]{Verdoolaege2005PhD}
 584 respectively.
 585
 586 The function \ai[\tt]{eadd} is an extension of the function
 587 \ai[\tt]{new\_eadd} from \shortciteN{Seghir2002}.
 588 Apart from supporting the additional types from Section~\ref{a:data},
 589 the new version also additionally imposes an order on the nesting of
 590 different \ai[\tt]{enode}s.
 591 Without such an ordering, \ai[\tt]{evalue}s could be constructed
 592 representing for example
 593 $$
 594 (0 y^ 0 + ( 0 x^0 + 1 x^1 ) y^1 ) x^0 + (0 y^0 - 1 y^1) x^1
 595 ,
 596 $$
 597 which is just a funny way of saying $0$.
 598
 599 \begin{verbatim}
 600 void eor(evalue *e1, evalue *res);
 601 \end{verbatim}
 602 The function \ai[\tt]{eor} implements the \ai{union}
 603 operation from \citeN[Section~4.5.3]{Verdoolaege2005PhD}.  Both arguments
 604 are assumed to correspond to indicator functions.
 605
 606 \begin{verbatim}
 607 evalue *esum(evalue *E, int nvar);
 608 evalue *evalue_sum(evalue *E, int nvar, unsigned MaxRays);
 609 \end{verbatim}
 610 The function \ai[\tt]{esum} has been superseded by
 611 \ai[\tt]{evalue\_sum}.
 612 The function \ai[\tt]{evalue\_sum} performs the summation
 613 operation from \citeN[Section~4.5.4]{Verdoolaege2005PhD}.
 614 The piecewise step-polynomial represented by \verb+E+ is summated
 615 over its first \verb+nvar+ variables.
 616 Note that \verb+E+ must be zero or of type \ai[\tt]{partition}.
 617 The function returns the result in a newly allocated
 618 \ai[\tt]{evalue}.
 619 Note also that \verb+E+ needs to have been converted
 620 from \ai[\tt]{fractional}s to \ai[\tt]{flooring}s using
 621 the function \ai[\tt]{evalue\_frac2floor}.
 622 \begin{verbatim}
 623 void evalue_frac2floor(evalue *e);
 624 \end{verbatim}
 625 This function also ensures that the arguments of the
 626 \ai[\tt]{flooring}s are positive in the relevant chambers.
 627 It currently assumes that the argument of each
 628 \ai[\tt]{fractional} in the original \ai[\tt]{evalue}
 629 has a minimum in the corresponding chamber.
 630
 631 \begin{verbatim}
 632 double compute_evalue(const evalue *e, Value *list_args);
 633 Value *compute_poly(Enumeration *en,Value *list_args);
 634 evalue *evalue_eval(const evalue *e, Value *values);
 635 \end{verbatim}
 636 The functions \ai[\tt]{compute\_evalue},
 637 \ai[\tt]{compute\_poly} and
 638 \ai[\tt]{evalue\_eval}
 639 evaluate a (piecewise) quasi-polynomial
 640 at a certain point.  The argument \verb+list_args+
 641 points to an array of \ai[\tt]{Value}s that is assumed
 642 to be long enough.
 643 The \verb+double+ return value of \ai[\tt]{compute\_evalue}
 644 is inherited from \PolyLib/.
 645
 646 \begin{verbatim}
 647 void print_evalue(FILE *DST, const evalue *e, char **pname);
 648 \end{verbatim}
 649 The function \ai[\tt]{print\_evalue} dumps a human-readable
 650 representation to the stream pointed to by \verb+DST+.
 651 The argument \verb+pname+ points
 652 to an array of character strings representing the parameter names.
 653 The array is assumed to be long enough.
 654
 655 \begin{verbatim}
 656 int eequal(const evalue *e1, const evalue *e2);
 657 \end{verbatim}
 658 The function \ai[\tt]{eequal} return true (\verb+1+) if its
 659 two arguments are structurally identical.
 660 I.e., it does {\em not\/} check whether the two
 661 (piecewise) quasi-polynomial represent the same function.
 662
 663 \begin{verbatim}
 664 void reduce_evalue (evalue *e);
 665 \end{verbatim}
 666 The function \ai[\tt]{reduce\_evalue} performs some
 667 simplifications on \ai[\tt]{evalue}s.
 668 Here, we only describe the simplifications that are directly
 669 related to the internal representation.
 670 Some other simplifications are explained in
 671 \citeN[Section~4.7.2]{Verdoolaege2005PhD}.
 672 If the highest order coefficients of a \ai[\tt]{polynomial},
 673 \ai[\tt]{fractional} or \ai[\tt]{flooring} are zero (possibly
 674 after some other simplifications), then the size of the array
 675 is reduced.  If only the constant term remains, i.e.,
 676 the size is reduced to $1$ for  \ai[\tt]{polynomial} or to $2$
 677 for the other types, then the whole node is replaced by
 678 the constant term.
 679 Additionally, if the argument of a \ai[\tt]{fractional}
 680 has been reduced to a constant, then the whole node
 681 is replaced by its partial evaluation.
 682 A \ai[\tt]{relation} is similarly reduced if its second
 683 branch or both its branches are zero.
 684 Chambers with zero associated quasi-polynomials are
 685 discarded from a \ai[\tt]{partition}.
 686
 687 \subsection{Generating Functions}
 688
 689 The representation of \rgf/s uses
 690 some basic types from the \ai[\tt]{NTL} library \shortcite{NTL}
 691 for representing arbitrary precision integers
 692 (\ai[\tt]{ZZ})
 693 as well as vectors (\ai[\tt]{vec\_ZZ}) and matrices (\ai[\tt]{mat\_ZZ})
 694 of such integers.
 695 We further introduces a type \ai[\tt]{QQ} for representing a rational
 696 number and use vectors (\ai[\tt]{vec\_QQ}) of such numbers.
 697 \begin{verbatim}
 698 struct QQ {
 699     ZZ  n;
 700     ZZ  d;
 701 };
 702
 703 NTL_vector_decl(QQ,vec_QQ);
 704 \end{verbatim}
 705
 706 Each term in a \rgf/ is represented by a \ai[\tt]{short\_rat}
 707 structure.
 708 \begin{verbatim}
 709 struct short_rat {
 710     struct {
 711         /* rows: terms in numerator */
 712         vec_QQ  coeff;
 713         mat_ZZ  power;
 714     } n;
 715     struct {
 716         /* rows: factors in denominator */
 717         mat_ZZ  power;
 718     } d;
 719 };
 720 \end{verbatim}
 721 The fields \ai[\tt]{n} and \ai[\tt]{d} represent the
 722 numerator and the denominator respectively.
 723 Note that in our implementation we combine terms
 724 with the same denominator.
 725 In the numerator, each element of \ai[\tt]{coeff} and each row of \ai[\tt]{power}
 726 represents a single such term.
 727 The vector \ai[\tt]{coeff} contains the rational coefficients
 728 $\alpha_i$ of each term.
 729 The columns of \ai[\tt]{power} correspond to the powers
 730 of the variables.
 731 In the denominator, each row of \ai[\tt]{power}
 732 corresponds to the power $\vec b_{ij}$ of a
 733 factor in the denominator.
 734
 735 \begin{example}
 736 Figure~\ref{fig:rat}
 737 shows the internal representation of
 738 $$
 739 \frac{\frac 3 2 \, x_0^2 x_1^3 + 2 \, x_0^5 x_1^{-7}}
 740 { (1 - x_0 x_1^{-3}) (1 - x_1^2)}
 741 .
 742 $$
 743
 744 \begin{figure}
 745 \begin{center}
 746 \begin{minipage}{0cm}
 747 \begin{xy}
 748 *\hbox{
 749 \tt
 750 \begin{tabular}{|c|c|c|}
 751 \hline
 752 n.coeff & 3 & 2 \\
 753 \cline{2-3}
 754         & 2 & 1 \\
 755 \hline
 756 n.power & 2 & 3 \\
 757 \cline{2-3}
 758         & 5 & -7 \\
 759 \hline
 760 d.power & 1 & -3 \\
 761 \cline{2-3}
 762         & 0 & 2 \\
 763 \hline
 764 \end{tabular}
 765 }+UC*++!D\hbox{\tt short\_rat}
 766 \end{xy}
 767 \end{minipage}
 768 \end{center}
 769 \caption{Representation of
 770 $
 771 \left(\frac 3 2 \, x_0^2 x_1^3 + 2 \, x_0^5 x_1^{-7}\right)
 772 / \left( (1 - x_0 x_1^{-3}) (1 - x_1^2)\right)
 773 $.}
 774 \label{fig:rat}
 775 \end{figure}
 776
 777 \end{example}
 778
 779 The whole \rgf/ is represented by a \ai[\tt]{gen\_fun}
 780 structure.
 781 \begin{verbatim}
 782 typedef std::set<short_rat *,
 783                  short_rat_lex_smaller_denominator > short_rat_list;
 784
 785 struct gen_fun {
 786     short_rat_list term;
 787     Polyhedron *context;
 788
 789     void add(const QQ& c, const vec_ZZ& num, const mat_ZZ& den);
 790     void add(short_rat *r);
 791     void add(const QQ& c, const gen_fun *gf,
 792                 barvinok_options *options);
 793     void substitute(Matrix *CP);
 794     gen_fun *Hadamard_product(const gen_fun *gf,
 795                               barvinok_options *options);
 796     void print(std::ostream& os,
 797                unsigned int nparam, char **param_name) const;
 798     operator evalue *() const;
 799     ZZ coefficient(Value* params, barvinok_options *options) const;
 800     void coefficient(Value* params, Value* c) const;
 801
 802     gen_fun(Polyhedron *C);
 803     gen_fun(Value c);
 804     gen_fun(const gen_fun *gf);
 805     ~gen_fun();
 806 };
 807 \end{verbatim}
 808 A new \ai[\tt]{gen\_fun} can be constructed either as empty \rgf/ (possibly
 809 with a given context \verb+C+), as a copy of an existing \rgf/ \verb+gf+, or as
 810 constant \rgf/ with value for the constant term specified by \verb+c+.
 811 \\
 812 The first \ai[\tt]{gen\_fun::add} method adds a new term to the \rgf/,
 813 described by the coefficient \verb+c+, the numerator \verb+num+ and the
 814 denominator \verb+den+.
 815 It makes all powers in the denominator lexico-positive,
 816 orders them in lexicographical order and inserts the new
 817 term in \ai[\tt]{term} according to the lexicographical
 818 order of the combined powers in the denominator.
 819 The second \ai[\tt]{gen\_fun::add} method adds \verb+c+ times \verb+gf+
 820 to the \rgf/.
 821 \\
 822 The method \ai[\tt]{gen\_fun::operator evalue *} performs
 823 the conversion from \rgf/ to \psp/ explained in
 824 \citeN[Section~4.5.5]{Verdoolaege2005PhD}.
 825 The \ai[\tt]{Polyhedron} \ai[\tt]{context} is the superset
 826 of all points where the enumerator is non-zero used during this conversion,
 827 i.e., it is the set $Q$ from \citeN[Equation~4.31]{Verdoolaege2005PhD}.
 828 If  \ai[\tt]{context} is \verb+NULL+ the maximal
 829 allowed context is assumed, i.e., the maximal
 830 region with lexico-positive rays.
 831 \\
 832 The method \ai[\tt]{gen\_fun::coefficient} computes the coefficient
 833 of the term with power given by \verb+params+ and stores the result
 834 in \verb+c+.
 835 This method performs essentially the same computations as
 836 \ai[\tt]{gen\_fun::operator evalue *}, except that it adds extra
 837 equality constraints based on the specified values for the power.
 838 \\
 839 The method \ai[\tt]{gen\_fun::substitute} performs the
 840 \ai{monomial substitution} specified by the homogeneous matrix \verb+CP+
 841 that maps a set of ``\ai{compressed parameter}s'' \shortcite{Meister2004PhD}
 842 to the original set of parameters.
 843 That is, if we are given a \rgf/ $G(\vec z)$ that encodes the
 844 explicit function $g(\vec i')$, where $\vec i'$ are the coordinates of
 845 the transformed space, and \verb+CP+ represents the map
 846 $\vec i = A \vec i' + \vec a$ back to the original space with coordinates $\vec i$,
 847 then this method transforms the \rgf/ to $F(\vec x)$ encoding the
 848 same explicit function $f(\vec i)$, i.e.,
 849 $$f(\vec i) = f(A \vec i' + \vec a) = g(\vec i ').$$
 850 This means that the coefficient of the term
 851 $\vec x^{\vec i} = \vec x^{A \vec i' + \vec a}$ in $F(\vec x)$ should be equal to the
 852 coefficient of the term $\vec z^{\vec i'}$ in $G(\vec z)$.
 853 In other words, if
 854 $$
 855 G(\vec z) =
 856 \sum_i \epsilon_i \frac{\vec z^{\vec v_i}}{\prod_j (1-\vec z^{\vec b_{ij}})}
 857 $$
 858 then
 859 $$
 860 F(\vec x) =
 861 \sum_i \epsilon_i \frac{\vec x^{A \vec v_i + \vec a}}
 862                        {\prod_j (1-\vec x^{A \vec b_{ij}})}
 863 .
 864 $$
 865 \\
 866 The method \ai[\tt]{gen\_fun::Hadamard\_product} computes the
 867 \ai{Hadamard product} of the current \rgf/ with the \rgf/ \verb+gf+,
 868 as explained in \citeN[Section~4.5.2]{Verdoolaege2005PhD}.
 869
 870 \subsection{Counting Functions}
 871 \label{a:counting:functions}
 872
 873 Our library provides essentially three different counting functions:
 874 one for non-parametric polytopes, one for parametric polytopes
 875 and one for parametric sets with existential variables.
 876 The old versions of these functions have a ``\ai[\tt]{MaxRays}''
 877 argument, while the new versions have a more general
 878 \ai[\tt]{barvinok\_options} argument.
 879 For more information on \ai[\tt]{barvinok\_options}, see Section~\ref{a:options}.
 880
 881 \begin{verbatim}
 882 void barvinok_count(Polyhedron *P, Value* result,
 883                     unsigned NbMaxCons);
 884 void barvinok_count_with_options(Polyhedron *P, Value* result,
 885                                  struct barvinok_options *options);
 886 \end{verbatim}
 887 The function \ai[\tt]{barvinok\_count} or
 888 \ai[\tt]{barvinok\_count\_with\_options} enumerates the non-parametric
 889 polytope \verb+P+ and returns the result in the \ai[\tt]{Value}
 890 pointed to by \verb+result+, which needs to have been allocated
 891 and initialized.
 892 If \verb+P+ is a union, then only the first set in the union will
 893 be taken into account.
 894 For the meaning of the argument \verb+NbMaxCons+, see
 895 the discussion on \ai[\tt]{MaxRays} in Section~\ref{a:options}.
 896
 897 The function \ai[\tt]{barvinok\_enumerate} for enumerating
 898 parametric polytopes was meant to be
 899 a drop-in replacement of \PolyLib/'s \ai[\tt]{Polyhedron\_Enumerate}
 900 function.
 901 Unfortunately, the latter has been changed to
 902 accept an extra argument in recent versions of \PolyLib/ as shown below.
 903 \begin{verbatim}
 904 Enumeration* barvinok_enumerate(Polyhedron *P, Polyhedron* C,
 905                                 unsigned MaxRays);
 906 extern Enumeration *Polyhedron_Enumerate(Polyhedron *P,
 907             Polyhedron *C, unsigned MAXRAYS, char **pname);
 908 \end{verbatim}
 909 The argument \verb+MaxRays+ has the same meaning as the argument
 910 \verb+NbMaxCons+ above.
 911 The argument \verb+P+ refers to the $(d+n)$-dimensional
 912 polyhedron defining the parametric polytope.
 913 The argument \verb+C+ is an $n$-dimensional polyhedron containing
 914 extra constraints on the parameter space.
 915 Its primary use is to indicate how many of the dimensions
 916 in \verb+P+ refer to parameters as any constraint in \verb+C+
 917 could equally well have been added to \verb+P+ itself.
 918 Note that the dimensions referring to the parameters should
 919 appear {\em last}.
 920 If either \verb+P+ or \verb+C+ is a union,
 921 then only the first set in the union will be taken into account.
 922 The result is a newly allocated \ai[\tt]{Enumeration}.
 923 As an alternative we also provide a function
 924 (\ai[\tt]{barvinok\_enumerate\_ev} or
 925 \ai[\tt]{barvinok\_enumerate\_with\_options}) that returns
 926 an \ai[\tt]{evalue}.
 927 \begin{verbatim}
 928 evalue* barvinok_enumerate_ev(Polyhedron *P, Polyhedron* C,
 929                               unsigned MaxRays);
 930 evalue* barvinok_enumerate_with_options(Polyhedron *P,
 931         Polyhedron* C, struct barvinok_options *options);
 932 \end{verbatim}
 933
 934 For enumerating parametric sets with existentially quantified variables,
 935 we provide two functions:
 936 \ai[\tt]{barvinok\_enumerate\_e},
 937 and
 938 \ai[\tt]{barvinok\_enumerate\_isl}.
 939 \begin{verbatim}
 940 evalue* barvinok_enumerate_e(Polyhedron *P,
 941           unsigned exist, unsigned nparam, unsigned MaxRays);
 942 evalue* barvinok_enumerate_e_with_options(Polyhedron *P,
 943           unsigned exist, unsigned nparam,
 944           struct barvinok_options *options);
 945 evalue *barvinok_enumerate_isl(Polyhedron *P,
 946           unsigned exist, unsigned nparam,
 947           struct barvinok_options *options);
 948 evalue *barvinok_enumerate_scarf(Polyhedron *P,
 949           unsigned exist, unsigned nparam,
 950           struct barvinok_options *options);
 951 \end{verbatim}
 952 The first function tries the simplification rules from
 953 \citeN[Section~4.6.2]{Verdoolaege2005PhD} before resorting to the method
 954 based on \indac{PIP} from \citeN[Section~4.6.3]{Verdoolaege2005PhD}.
 955 The second function immediately applies the technique from
 956 \citeN[Section~4.6.3]{Verdoolaege2005PhD}.
 957 The argument \verb+exist+ refers to the number of existential variables,
 958 whereas
 959 the argument \verb+nparam+ refers to the number of parameters.
 960 The order of the dimensions in \verb+P+ is:
 961 counted variables first, then existential variables and finally
 962 the parameters.
 963 The function \ai[\tt]{barvinok\_enumerate\_scarf} performs the same
 964 computation as the function \ai[\tt]{barvinok\_enumerate\_scarf\_series}
 965 below, but produces an explicit representation instead of a generating function.
 966
 967 \begin{verbatim}
 968 gen_fun * barvinok_series(Polyhedron *P, Polyhedron* C,
 969                           unsigned MaxRays);
 970 gen_fun * barvinok_series_with_options(Polyhedron *P,
 971     Polyhedron* C, barvinok_options *options);
 972 gen_fun *barvinok_enumerate_e_series(Polyhedron *P,
 973                   unsigned exist, unsigned nparam,
 974                   barvinok_options *options);
 975 gen_fun *barvinok_enumerate_scarf_series(Polyhedron *P,
 976                           unsigned exist, unsigned nparam,
 977                           barvinok_options *options);
 978 \end{verbatim}
 979 The function
 980 \ai[\tt]{barvinok\_series} or
 981 \ai[\tt]{barvinok\_series\_with\_options} enumerates parametric polytopes
 982 in the form of a \rgf/.
 983 The polyhedron \verb+P+ is assumed to have only
 984 revlex-positive rays.
 985 \\
 986 The function \ai[\tt]{barvinok\_enumerate\_e\_series} computes a
 987 generating function for the number of point in the parametric set
 988 defined by \verb+P+ with \verb+exist+ existentially quantified
 989 variables using the \ai{projection theorem}, as explained
 990 in \autoref{s:projection}.
 991 The function \ai[\tt]{barvinok\_enumerate\_scarf\_series} computes a
 992 generating function for the number of point in the parametric set
 993 defined by \verb+P+ with \verb+exist+ existentially quantified
 994 variables, which is assumed to be 2.
 995 This function implements the technique of
 996 \shortciteN{Scarf2006Neighborhood} using the \ai{neighborhood complex}
 997 description of \shortciteN{Scarf1981indivisibilities:II}.
 998 It is currently restricted to problems with 3 or 4 constraints involving
 999 the existentially quantified variables.
1000
1001 \subsection{Auxiliary Functions}
1002
1003 In this section we briefly mention some auxiliary functions
1004 available in the \barvinok/ library.
1005
1006 \begin{verbatim}
1007 void Polyhedron_Polarize(Polyhedron *P);
1008 \end{verbatim}
1009 The function \ai[\tt]{Polyhedron\_Polarize}
1010 polarizes its argument and is explained
1011 in \citeN[Section~4.4.2]{Verdoolaege2005PhD}.
1012
1013 \begin{verbatim}
1014 int unimodular_complete(Matrix *M, int row);
1015 \end{verbatim}
1016 The function \ai[\tt]{unimodular\_complete} extends
1017 the first \verb+row+ rows of
1018 \verb+M+ with an integral basis of the orthogonal complement
1019 as explained in Section~\ref{s:completion}.
1020 Returns non-zero
1021 if the resulting matrix is unimodular\index{unimodular matrix}.
1022
1023 \begin{verbatim}
1024 int DomainIncludes(Polyhedron *D1, Polyhedron *D2);
1025 \end{verbatim}
1026 The function \ai[\tt]{DomainIncludes} extends
1027 the function \ai[\tt]{PolyhedronIncludes}
1028 provided by \PolyLib/
1029 to unions of polyhedra.
1030 It checks whether every polyhedron in the union {\tt D2}
1031 is included in some polyhedron of {\tt D1}.
1032
1033 \begin{verbatim}
1034 Polyhedron *DomainConstraintSimplify(Polyhedron *P,
1035                                      unsigned MaxRays);
1036 \end{verbatim}
1037 The value returned by
1038 \ai[\tt]{DomainConstraintSimplify} is a pointer to
1039 a newly allocated \ai[\tt]{Polyhedron} that contains the
1040 same integer points as its first argument but possibly
1041 has simpler constraints.
1042 Each constraint $ g \sp a x \ge c $
1043 is replaced by $ \sp a x \ge \ceil{ \frac c g } $,
1044 where $g$ is the \ac{gcd} of the coefficients in the original
1045 constraint.
1046 The \ai[\tt]{Polyhedron} pointed to by \verb+P+ is destroyed.
1047
1048 \begin{verbatim}
1049 Polyhedron* Polyhedron_Project(Polyhedron *P, int dim);
1050 \end{verbatim}
1051 The function \ai[\tt]{Polyhedron\_Project} projects
1052 \verb+P+ onto its last \verb+dim+ dimensions.
1053
1054 \begin{verbatim}
1055 Matrix *left_inverse(Matrix *M, Matrix **Eq);
1056 \end{verbatim}
1057 The \ai[\tt]{left\_inverse} function computes the left inverse
1058 of \verb+M+ as explained in Section~\ref{s:inverse}.
1059
1060 \sindex{reduced}{basis}
1061 \sindex{generalized}{reduced basis}
1062 \begin{verbatim}
1063 Matrix *Polyhedron_Reduced_Basis(Polyhedron *P,
1064                                  struct barvinok_options *options);
1065 \end{verbatim}
1066 \ai[\tt]{Polyhedron\_Reduced\_Basis} computes
1067 a \ai{generalized reduced basis} of {\tt P}, which
1068 is assumed to be a polytope, using the algorithm
1069 of~\shortciteN{Cook1993implementation}.
1070 See \autoref{s:feasibility} for more information.
1071 The basis vectors are stored in the rows of the matrix returned.
1072
1073 \begin{verbatim}
1074 Vector *Polyhedron_Sample(Polyhedron *P,
1075                           struct barvinok_options *options);
1076 \end{verbatim}
1077 \ai[\tt]{Polyhedron\_Sample} returns an \ai{integer point} of {\tt P}
1078 or {\tt NULL} if {\tt P} contains no integer points.
1079 The integer point is found using the algorithm
1080 of~\shortciteN{Cook1993implementation} and uses
1081 \ai[\tt]{Polyhedron\_Reduced\_Basis} to compute the reduced bases.
1082 See \autoref{s:feasibility} for more information.