doc/Internal.tex

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