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     /* bernstein options */
 269     #define     BV_BERNSTEIN_NONE   0
 270     #define     BV_BERNSTEIN_MAX    1
 271     #define     BV_BERNSTEIN_MIN   -1
 272     int         bernstein_optimize;
 273
 274     #define     BV_BERNSTEIN_FACTORS    1
 275     #define     BV_BERNSTEIN_INTERVALS  2
 276     int         bernstein_recurse;
 277
 278     #define     BV_LP_POLYLIB           0
 279     #define     BV_LP_GLPK              1
 280     #define     BV_LP_CDD               2
 281     #define     BV_LP_CDDF              3
 282     #define     BV_LP_PIP               4
 283     int         lp_solver;
 284
 285     #define     BV_HULL_GBR             0
 286     #define     BV_HULL_HILBERT         1
 287     int         integer_hull;
 288 };
 289
 290 struct barvinok_options *barvinok_options_new_with_defaults();
 291 \end{verbatim}
 292
 293 The function \ai[\tt]{barvinok\_options\_new\_with\_defaults}
 294 can be used to create a \ai[\tt]{barvinok\_options} structure
 295 with default values.
 296
 297 \begin{itemize}
 298 \item \PolyLib/ options
 299
 300 \begin{itemize}
 301
 302 \item \ai[\tt]{MaxRays}
 303
 304 The value of \ai[\tt]{MaxRays} is passed to various \PolyLib/
 305 functions and defines the
 306 maximum size of a table used in the \ai{double description} computation
 307 in the \PolyLib/ function \ai[\tt]{Chernikova}.
 308 In earlier versions of \PolyLib/,
 309 this parameter had to be conservatively set
 310 to a high number to ensure successful operation,
 311 resulting in significant memory overhead.
 312 Our change to allow this table to grow
 313 dynamically is available in recent versions of \PolyLib/.
 314 In these versions, the value no longer indicates the maximal
 315 table size, but rather the size of the initial allocation.
 316 This value may be set to \verb+0+ or left as set
 317 by \ai[\tt]{barvinok\_options\_new\_with\_defaults}.
 318
 319 \end{itemize}
 320
 321 \item \ai[\tt]{NTL} options
 322
 323 \begin{itemize}
 324
 325 \item \ai[\tt]{LLL\_a}
 326 \item \ai[\tt]{LLL\_b}
 327
 328 The values used for the \ai{reduction parameter}
 329 in the call to \ai[\tt]{NTL}'s implementation of \indac{LLL}.
 330
 331 \end{itemize}
 332
 333 \item \ai[\tt]{barvinok} specific options
 334
 335 \begin{itemize}
 336
 337 \item \ai[\tt]{incremental\_specialization}
 338
 339 Selects the \ai{specialization} algorithm to be used.
 340 If set to {\tt 0} then a direct specialization is performed
 341 using a random vector.
 342 Value {\tt 1} selects a depth first incremental specialization,
 343 while value {\tt 2} selects a breadth first incremental specialization.
 344 The default is selected by the \ai[\tt]{--enable-incremental}
 345 \ai[\tt]{configure} option.
 346 For more information we refer to~\citeN[Section~4.4.3]{Verdoolaege2005PhD}.
 347
 348 \end{itemize}
 349
 350 \end{itemize}
 351
 352 \subsection{Data Structures for Quasi-polynomials}
 353 \label{a:data}
 354
 355 Internally, we do not represent our \ai{quasi-polynomial}s
 356 as step-polynomials, but instead as polynomials of
 357 fractional parts of degree-$1$ polynomials.
 358 However, we also allow our quasi-polynomials to be represented
 359 as polynomials with periodic numbers for coefficients,
 360 similarly to \shortciteN{Loechner1999}.
 361 By default, the current version of \barvinok/ uses
 362 \ai[\tt]{fractional}s, but this can be changed through
 363 the \ai[\tt]{--disable-fractional} configure option.
 364 When this option is specified, the periodic numbers
 365 are represented as
 366 an explicit enumeration using the \ai[\tt]{periodic} type.
 367 A quasi-polynomial based on fractional
 368 parts can also be converted to an actual step-polynomial
 369 using \ai[\tt]{evalue\_frac2floor}, but this is not fully
 370 supported yet.
 371
 372 For reasons of compatibility,%
 373 \footnote{Also known as laziness.}
 374 we shoehorned our representations for piecewise quasi-polynomials
 375 into the existing data structures.
 376 To this effect, we introduced four new types,
 377 \ai[\tt]{fractional}, \ai[\tt]{relation},
 378 \ai[\tt]{partition} and \ai[\tt]{flooring}.
 379 \begin{verbatim}
 380 typedef enum { polynomial, periodic, evector, fractional,
 381                relation, partition, flooring } enode_type;
 382 \end{verbatim}
 383 The field \ai[\tt]{pos} is not used in most of these
 384 additional types and is therefore set to \verb+-1+.
 385
 386 The types \ai[\tt]{fractional} and \ai[\tt]{flooring}
 387 represent polynomial expressions in a fractional part or a floor respectively.
 388 The generator is stored in \verb+arr[0]+, while the
 389 coefficients are stored in the remaining array elements.
 390 That is, an \ai[\tt]{enode} of type \ai[\tt]{fractional}
 391 represents
 392 $$
 393 \verb+arr[1]+ + \verb+arr[2]+ \{\verb+arr[0]+\} +
 394 \verb+arr[3]+ \{\verb+arr[0]+\}^2 + \cdots +
 395 \verb+arr[l-1]+ \{\verb+arr[0]+\}^{l-2}
 396 .
 397 $$
 398 An \ai[\tt]{enode} of type \ai[\tt]{flooring}
 399 represents
 400 $$
 401 \verb+arr[1]+ + \verb+arr[2]+ \lfloor\verb+arr[0]+\rfloor +
 402 \verb+arr[3]+ \lfloor\verb+arr[0]+\rfloor^2 + \cdots +
 403 \verb+arr[l-1]+ \lfloor\verb+arr[0]+\rfloor^{l-2}
 404 .
 405 $$
 406
 407 \begin{example}
 408 The internal representation of the quasi-polynomial
 409 $$\left(1+2 \left\{\frac p 2\right\}\right) p^2 + 3 p + \frac 5 2$$
 410 is shown in Figure~\ref{f:fractional}.
 411
 412 \begin{figure}
 413 \begin{xy}
 414 \POS(0,0)*!UL{\hbox{
 415 \tt
 416 \begin{tabular}{|c|c|c|}
 417 \hline
 418 \multicolumn{2}{|c|}{type} & polynomial \\
 419 \hline
 420 \multicolumn{2}{|c|}{size} & 3 \\
 421 \hline
 422 \multicolumn{2}{|c|}{pos} & 1 \\
 423 \hline
 424 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 2 \\
 425 \cline{2-3}
 426        & x.n & 5 \\
 427 \hline
 428 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\
 429 \cline{2-3}
 430        & x.n & 3 \\
 431 \hline
 432 \smash{\lower 6.25pt\hbox{arr[2]}} & d & 0 \\
 433 \cline{2-3}
 434        & x.p &   \\
 435 \hline
 436 \end{tabular}
 437 }
 438 }="box1"
 439 +DR*!DR\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial}\hskip 1.5\tabcolsep}+C="a"
 440 \POS(60,0)*!UL{\hbox{
 441 \tt
 442 \begin{tabular}{|c|c|c|}
 443 \hline
 444 \multicolumn{2}{|c|}{type} & fractional \\
 445 \hline
 446 \multicolumn{2}{|c|}{size} & 3 \\
 447 \hline
 448 \multicolumn{2}{|c|}{pos} & -1 \\
 449 \hline
 450 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 0 \\
 451 \cline{2-3}
 452        & x.p &   \\
 453 \hline
 454 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\
 455 \cline{2-3}
 456        & x.n & 1 \\
 457 \hline
 458 \smash{\lower 6.25pt\hbox{arr[2]}} & d & 1 \\
 459 \cline{2-3}
 460        & x.n & 2 \\
 461 \hline
 462 \end{tabular}
 463 }
 464 }="box2"
 465 +UL+<0.5\tabcolsep,0pt>*!UL\hbox{\strut}+CL="b"
 466 \POS"a"\ar@(r,l) "b"
 467 \POS"box2"+UR*!UR{\hbox{
 468 \tt
 469 \begin{tabular}{|c|}
 470 \hline
 471  fractional \\
 472 \hline
 473  3 \\
 474 \hline
 475  -1 \\
 476 \hline
 477  0 \\
 478 \hline
 479 \end{tabular}
 480 }
 481 }+CD*!U{\strut}+C="c"
 482 \POS(60,-50)*!UL{\hbox{
 483 \tt
 484 \begin{tabular}{|c|c|c|}
 485 \hline
 486 \multicolumn{2}{|c|}{type} & polynomial \\
 487 \hline
 488 \multicolumn{2}{|c|}{size} & 2 \\
 489 \hline
 490 \multicolumn{2}{|c|}{pos} & 1 \\
 491 \hline
 492 \smash{\lower 6.25pt\hbox{arr[0]}} & d & 1 \\
 493 \cline{2-3}
 494        & x.n & 0 \\
 495 \hline
 496 \smash{\lower 6.25pt\hbox{arr[1]}} & d & 2 \\
 497 \cline{2-3}
 498        & x.n & 1 \\
 499 \hline
 500 \end{tabular}
 501 }
 502 }="box3"
 503 +UR-<0.8\tabcolsep,0pt>*!UR\hbox{\strut}+CR="d"
 504 \POS"c"\ar@(r,r) "d"
 505 \POS"box1"+UC*++!D\hbox{\tt enode}
 506 \POS"box2"+UC*++!D\hbox{\tt enode}
 507 \POS"box3"+UC*++!D\hbox{\tt enode}
 508 \end{xy}
 509 \caption{The quasi-polynomial
 510 $\left(1+2 \left\{\frac p 2\right\}\right) p^2 + 3 p + \frac 5 2$.}
 511 \label{f:fractional}
 512 \end{figure}
 513
 514 \end{example}
 515
 516 The \ai[\tt]{relation} type is used to represent \ai{stride}s.
 517 In particular, if the value of \ai[\tt]{size} is 2, then
 518 the value of a \ai[\tt]{relation} is (in pseudo-code):
 519 \begin{verbatim}
 520 (value(arr[0]) == 0) ? value(arr[1]) : 0
 521 \end{verbatim}
 522 If the size is 3, then the value is:
 523 \begin{verbatim}
 524 (value(arr[0]) == 0) ? value(arr[1]) : value(arr[2])
 525 \end{verbatim}
 526 The type of \verb+arr[0]+ is typically \ai[\tt]{fractional}.
 527
 528 Finally, the \ai[\tt]{partition} type is used to
 529 represent piecewise quasi-polynomials.
 530 We prefer to encode this information inside \ai[\tt]{evalue}s
 531 themselves
 532 rather than using \ai[\tt]{Enumeration}s since we want
 533 to perform the same kinds of operations on both quasi-polynomials
 534 and piecewise quasi-polynomials.
 535 An \ai[\tt]{enode} of type \ai[\tt]{partition} may not be nested
 536 inside another \ai[\tt]{enode}.
 537 The size of the array is twice the number of ``chambers''.
 538 Pointers to chambers are stored in the even slots,
 539 whereas pointer to the associated quasi-polynomials
 540 are stored in the odd slots.
 541 To be able to store pointers to chambers, the
 542 definition of \ai[\tt]{evalue} was changed as follows.
 543 \begin{verbatim}
 544 typedef struct _evalue {
 545   Value d;              /* denominator */
 546   union {
 547     Value n;            /* numerator (if denominator > 0) */
 548     struct _enode *p;   /* pointer   (if denominator == 0) */
 549     Polyhedron *D;      /* domain    (if denominator == -1) */
 550   } x;
 551 } evalue;
 552 \end{verbatim}
 553 Note that we allow a ``chamber'' to be a union of polyhedra
 554 as discussed in \citeN[Section~4.5.1]{Verdoolaege2005PhD}.
 555 Chambers with extra variables, i.e., those of
 556 \citeN[Section~4.6.5]{Verdoolaege2005PhD},
 557 are only partially supported.
 558 The field \ai[\tt]{pos} is set to the actual dimension,
 559 i.e., the number of parameters.
 560
 561 \subsection{Operations on Quasi-polynomials}
 562 \label{a:operations}
 563
 564 In this section we discuss some of the more important
 565 operations on \ai[\tt]{evalue}s provided by the
 566 \barvinok/ library.
 567 Some of these operations are extensions
 568 of the functions from \PolyLib/ with the same name.
 569
 570 Most of these operation are also provided by \isl/ on
 571 \ai[\tt]{isl\_pw\_qpolynomial}s, which are set to replace
 572 \ai[\tt]{evalue}s.  Use \ai[\tt]{isl\_pw\_qpolynomial\_from\_evalue} to convert
 573 from \ai[\tt]{evalue}s to \ai[\tt]{isl\_pw\_qpolynomial}s.
 574 \begin{verbatim}
 575 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_evalue(
 576         __isl_take isl_dim *dim, const evalue *e);
 577 \end{verbatim}
 578
 579 \begin{verbatim}
 580 void eadd(const evalue *e1,evalue *res);
 581 void emul(const evalue *e1, evalue *res);
 582 \end{verbatim}
 583 The functions \ai[\tt]{eadd} and \ai[\tt]{emul} takes
 584 two (pointers to) \ai[\tt]{evalue}s \verb+e1+ and \verb+res+
 585 and computes their sum and product respectively.
 586 The result is stored in \verb+res+, overwriting (and deallocating)
 587 the original value of \verb+res+.
 588 It is an error if exactly one of
 589 the arguments of \ai[\tt]{eadd} is of type \ai[\tt]{partition}
 590 (unless the other argument is \verb+0+).
 591 The addition and multiplication operations are described
 592 in \citeN[Section~4.5.1]{Verdoolaege2005PhD}
 593 and~\citeN[Section~4.5.2]{Verdoolaege2005PhD}
 594 respectively.
 595
 596 The function \ai[\tt]{eadd} is an extension of the function
 597 \ai[\tt]{new\_eadd} from \shortciteN{Seghir2002}.
 598 Apart from supporting the additional types from Section~\ref{a:data},
 599 the new version also additionally imposes an order on the nesting of
 600 different \ai[\tt]{enode}s.
 601 Without such an ordering, \ai[\tt]{evalue}s could be constructed
 602 representing for example
 603 $$
 604 (0 y^ 0 + ( 0 x^0 + 1 x^1 ) y^1 ) x^0 + (0 y^0 - 1 y^1) x^1
 605 ,
 606 $$
 607 which is just a funny way of saying $0$.
 608
 609 \begin{verbatim}
 610 void eor(evalue *e1, evalue *res);
 611 \end{verbatim}
 612 The function \ai[\tt]{eor} implements the \ai{union}
 613 operation from \citeN[Section~4.5.3]{Verdoolaege2005PhD}.  Both arguments
 614 are assumed to correspond to indicator functions.
 615
 616 \begin{verbatim}
 617 evalue *esum(evalue *E, int nvar);
 618 evalue *evalue_sum(evalue *E, int nvar, unsigned MaxRays);
 619 \end{verbatim}
 620 The function \ai[\tt]{esum} has been superseded by
 621 \ai[\tt]{evalue\_sum}.
 622 The function \ai[\tt]{evalue\_sum} performs the summation
 623 operation from \citeN[Section~4.5.4]{Verdoolaege2005PhD}.
 624 The piecewise step-polynomial represented by \verb+E+ is summated
 625 over its first \verb+nvar+ variables.
 626 Note that \verb+E+ must be zero or of type \ai[\tt]{partition}.
 627 The function returns the result in a newly allocated
 628 \ai[\tt]{evalue}.
 629 Note also that \verb+E+ needs to have been converted
 630 from \ai[\tt]{fractional}s to \ai[\tt]{flooring}s using
 631 the function \ai[\tt]{evalue\_frac2floor}.
 632 \begin{verbatim}
 633 void evalue_frac2floor(evalue *e);
 634 \end{verbatim}
 635 This function also ensures that the arguments of the
 636 \ai[\tt]{flooring}s are positive in the relevant chambers.
 637 It currently assumes that the argument of each
 638 \ai[\tt]{fractional} in the original \ai[\tt]{evalue}
 639 has a minimum in the corresponding chamber.
 640
 641 \begin{verbatim}
 642 double compute_evalue(const evalue *e, Value *list_args);
 643 Value *compute_poly(Enumeration *en,Value *list_args);
 644 evalue *evalue_eval(const evalue *e, Value *values);
 645 \end{verbatim}
 646 The functions \ai[\tt]{compute\_evalue},
 647 \ai[\tt]{compute\_poly} and
 648 \ai[\tt]{evalue\_eval}
 649 evaluate a (piecewise) quasi-polynomial
 650 at a certain point.  The argument \verb+list_args+
 651 points to an array of \ai[\tt]{Value}s that is assumed
 652 to be long enough.
 653 The \verb+double+ return value of \ai[\tt]{compute\_evalue}
 654 is inherited from \PolyLib/.
 655
 656 \begin{verbatim}
 657 void print_evalue(FILE *DST, const evalue *e, char **pname);
 658 \end{verbatim}
 659 The function \ai[\tt]{print\_evalue} dumps a human-readable
 660 representation to the stream pointed to by \verb+DST+.
 661 The argument \verb+pname+ points
 662 to an array of character strings representing the parameter names.
 663 The array is assumed to be long enough.
 664
 665 \begin{verbatim}
 666 int eequal(const evalue *e1, const evalue *e2);
 667 \end{verbatim}
 668 The function \ai[\tt]{eequal} return true (\verb+1+) if its
 669 two arguments are structurally identical.
 670 I.e., it does {\em not\/} check whether the two
 671 (piecewise) quasi-polynomial represent the same function.
 672
 673 \begin{verbatim}
 674 void reduce_evalue (evalue *e);
 675 \end{verbatim}
 676 The function \ai[\tt]{reduce\_evalue} performs some
 677 simplifications on \ai[\tt]{evalue}s.
 678 Here, we only describe the simplifications that are directly
 679 related to the internal representation.
 680 Some other simplifications are explained in
 681 \citeN[Section~4.7.2]{Verdoolaege2005PhD}.
 682 If the highest order coefficients of a \ai[\tt]{polynomial},
 683 \ai[\tt]{fractional} or \ai[\tt]{flooring} are zero (possibly
 684 after some other simplifications), then the size of the array
 685 is reduced.  If only the constant term remains, i.e.,
 686 the size is reduced to $1$ for  \ai[\tt]{polynomial} or to $2$
 687 for the other types, then the whole node is replaced by
 688 the constant term.
 689 Additionally, if the argument of a \ai[\tt]{fractional}
 690 has been reduced to a constant, then the whole node
 691 is replaced by its partial evaluation.
 692 A \ai[\tt]{relation} is similarly reduced if its second
 693 branch or both its branches are zero.
 694 Chambers with zero associated quasi-polynomials are
 695 discarded from a \ai[\tt]{partition}.
 696
 697 \subsection{Generating Functions}
 698
 699 The representation of \rgf/s uses
 700 some basic types from the \ai[\tt]{NTL} library \shortcite{NTL}
 701 for representing arbitrary precision integers
 702 (\ai[\tt]{ZZ})
 703 as well as vectors (\ai[\tt]{vec\_ZZ}) and matrices (\ai[\tt]{mat\_ZZ})
 704 of such integers.
 705 We further introduces a type \ai[\tt]{QQ} for representing a rational
 706 number and use vectors (\ai[\tt]{vec\_QQ}) of such numbers.
 707 \begin{verbatim}
 708 struct QQ {
 709     ZZ  n;
 710     ZZ  d;
 711 };
 712
 713 NTL_vector_decl(QQ,vec_QQ);
 714 \end{verbatim}
 715
 716 Each term in a \rgf/ is represented by a \ai[\tt]{short\_rat}
 717 structure.
 718 \begin{verbatim}
 719 struct short_rat {
 720     struct {
 721         /* rows: terms in numerator */
 722         vec_QQ  coeff;
 723         mat_ZZ  power;
 724     } n;
 725     struct {
 726         /* rows: factors in denominator */
 727         mat_ZZ  power;
 728     } d;
 729 };
 730 \end{verbatim}
 731 The fields \ai[\tt]{n} and \ai[\tt]{d} represent the
 732 numerator and the denominator respectively.
 733 Note that in our implementation we combine terms
 734 with the same denominator.
 735 In the numerator, each element of \ai[\tt]{coeff} and each row of \ai[\tt]{power}
 736 represents a single such term.
 737 The vector \ai[\tt]{coeff} contains the rational coefficients
 738 $\alpha_i$ of each term.
 739 The columns of \ai[\tt]{power} correspond to the powers
 740 of the variables.
 741 In the denominator, each row of \ai[\tt]{power}
 742 corresponds to the power $\vec b_{ij}$ of a
 743 factor in the denominator.
 744
 745 \begin{example}
 746 Figure~\ref{fig:rat}
 747 shows the internal representation of
 748 $$
 749 \frac{\frac 3 2 \, x_0^2 x_1^3 + 2 \, x_0^5 x_1^{-7}}
 750 { (1 - x_0 x_1^{-3}) (1 - x_1^2)}
 751 .
 752 $$
 753
 754 \begin{figure}
 755 \begin{center}
 756 \begin{minipage}{0cm}
 757 \begin{xy}
 758 *\hbox{
 759 \tt
 760 \begin{tabular}{|c|c|c|}
 761 \hline
 762 n.coeff & 3 & 2 \\
 763 \cline{2-3}
 764         & 2 & 1 \\
 765 \hline
 766 n.power & 2 & 3 \\
 767 \cline{2-3}
 768         & 5 & -7 \\
 769 \hline
 770 d.power & 1 & -3 \\
 771 \cline{2-3}
 772         & 0 & 2 \\
 773 \hline
 774 \end{tabular}
 775 }+UC*++!D\hbox{\tt short\_rat}
 776 \end{xy}
 777 \end{minipage}
 778 \end{center}
 779 \caption{Representation of
 780 $
 781 \left(\frac 3 2 \, x_0^2 x_1^3 + 2 \, x_0^5 x_1^{-7}\right)
 782 / \left( (1 - x_0 x_1^{-3}) (1 - x_1^2)\right)
 783 $.}
 784 \label{fig:rat}
 785 \end{figure}
 786
 787 \end{example}
 788
 789 The whole \rgf/ is represented by a \ai[\tt]{gen\_fun}
 790 structure.
 791 \begin{verbatim}
 792 typedef std::set<short_rat *,
 793                  short_rat_lex_smaller_denominator > short_rat_list;
 794
 795 struct gen_fun {
 796     short_rat_list term;
 797     Polyhedron *context;
 798
 799     void add(const QQ& c, const vec_ZZ& num, const mat_ZZ& den);
 800     void add(short_rat *r);
 801     void add(const QQ& c, const gen_fun *gf,
 802                 barvinok_options *options);
 803     void substitute(Matrix *CP);
 804     gen_fun *Hadamard_product(const gen_fun *gf,
 805                               barvinok_options *options);
 806     void print(std::ostream& os,
 807                unsigned int nparam, char **param_name) const;
 808     operator evalue *() const;
 809     ZZ coefficient(Value* params, barvinok_options *options) const;
 810     void coefficient(Value* params, Value* c) const;
 811
 812     gen_fun(Polyhedron *C);
 813     gen_fun(Value c);
 814     gen_fun(const gen_fun *gf);
 815     ~gen_fun();
 816 };
 817 \end{verbatim}
 818 A new \ai[\tt]{gen\_fun} can be constructed either as empty \rgf/ (possibly
 819 with a given context \verb+C+), as a copy of an existing \rgf/ \verb+gf+, or as
 820 constant \rgf/ with value for the constant term specified by \verb+c+.
 821 \\
 822 The first \ai[\tt]{gen\_fun::add} method adds a new term to the \rgf/,
 823 described by the coefficient \verb+c+, the numerator \verb+num+ and the
 824 denominator \verb+den+.
 825 It makes all powers in the denominator lexico-positive,
 826 orders them in lexicographical order and inserts the new
 827 term in \ai[\tt]{term} according to the lexicographical
 828 order of the combined powers in the denominator.
 829 The second \ai[\tt]{gen\_fun::add} method adds \verb+c+ times \verb+gf+
 830 to the \rgf/.
 831 \\
 832 The method \ai[\tt]{gen\_fun::operator evalue *} performs
 833 the conversion from \rgf/ to \psp/ explained in
 834 \citeN[Section~4.5.5]{Verdoolaege2005PhD}.
 835 The \ai[\tt]{Polyhedron} \ai[\tt]{context} is the superset
 836 of all points where the enumerator is non-zero used during this conversion,
 837 i.e., it is the set $Q$ from \citeN[Equation~4.31]{Verdoolaege2005PhD}.
 838 If  \ai[\tt]{context} is \verb+NULL+ the maximal
 839 allowed context is assumed, i.e., the maximal
 840 region with lexico-positive rays.
 841 \\
 842 The method \ai[\tt]{gen\_fun::coefficient} computes the coefficient
 843 of the term with power given by \verb+params+ and stores the result
 844 in \verb+c+.
 845 This method performs essentially the same computations as
 846 \ai[\tt]{gen\_fun::operator evalue *}, except that it adds extra
 847 equality constraints based on the specified values for the power.
 848 \\
 849 The method \ai[\tt]{gen\_fun::substitute} performs the
 850 \ai{monomial substitution} specified by the homogeneous matrix \verb+CP+
 851 that maps a set of ``\ai{compressed parameter}s'' \shortcite{Meister2004PhD}
 852 to the original set of parameters.
 853 That is, if we are given a \rgf/ $G(\vec z)$ that encodes the
 854 explicit function $g(\vec i')$, where $\vec i'$ are the coordinates of
 855 the transformed space, and \verb+CP+ represents the map
 856 $\vec i = A \vec i' + \vec a$ back to the original space with coordinates $\vec i$,
 857 then this method transforms the \rgf/ to $F(\vec x)$ encoding the
 858 same explicit function $f(\vec i)$, i.e.,
 859 $$f(\vec i) = f(A \vec i' + \vec a) = g(\vec i ').$$
 860 This means that the coefficient of the term
 861 $\vec x^{\vec i} = \vec x^{A \vec i' + \vec a}$ in $F(\vec x)$ should be equal to the
 862 coefficient of the term $\vec z^{\vec i'}$ in $G(\vec z)$.
 863 In other words, if
 864 $$
 865 G(\vec z) =
 866 \sum_i \epsilon_i \frac{\vec z^{\vec v_i}}{\prod_j (1-\vec z^{\vec b_{ij}})}
 867 $$
 868 then
 869 $$
 870 F(\vec x) =
 871 \sum_i \epsilon_i \frac{\vec x^{A \vec v_i + \vec a}}
 872                        {\prod_j (1-\vec x^{A \vec b_{ij}})}
 873 .
 874 $$
 875 \\
 876 The method \ai[\tt]{gen\_fun::Hadamard\_product} computes the
 877 \ai{Hadamard product} of the current \rgf/ with the \rgf/ \verb+gf+,
 878 as explained in \citeN[Section~4.5.2]{Verdoolaege2005PhD}.
 879
 880 \subsection{Counting Functions}
 881 \label{a:counting:functions}
 882
 883 Our library provides essentially three different counting functions:
 884 one for non-parametric polytopes, one for parametric polytopes
 885 and one for parametric sets with existential variables.
 886 The old versions of these functions have a ``\ai[\tt]{MaxRays}''
 887 argument, while the new versions have a more general
 888 \ai[\tt]{barvinok\_options} argument.
 889 For more information on \ai[\tt]{barvinok\_options}, see Section~\ref{a:options}.
 890
 891 \begin{verbatim}
 892 void barvinok_count(Polyhedron *P, Value* result,
 893                     unsigned NbMaxCons);
 894 void barvinok_count_with_options(Polyhedron *P, Value* result,
 895                                  struct barvinok_options *options);
 896 \end{verbatim}
 897 The function \ai[\tt]{barvinok\_count} or
 898 \ai[\tt]{barvinok\_count\_with\_options} enumerates the non-parametric
 899 polytope \verb+P+ and returns the result in the \ai[\tt]{Value}
 900 pointed to by \verb+result+, which needs to have been allocated
 901 and initialized.
 902 If \verb+P+ is a union, then only the first set in the union will
 903 be taken into account.
 904 For the meaning of the argument \verb+NbMaxCons+, see
 905 the discussion on \ai[\tt]{MaxRays} in Section~\ref{a:options}.
 906
 907 The function \ai[\tt]{barvinok\_enumerate} for enumerating
 908 parametric polytopes was meant to be
 909 a drop-in replacement of \PolyLib/'s \ai[\tt]{Polyhedron\_Enumerate}
 910 function.
 911 Unfortunately, the latter has been changed to
 912 accept an extra argument in recent versions of \PolyLib/ as shown below.
 913 \begin{verbatim}
 914 Enumeration* barvinok_enumerate(Polyhedron *P, Polyhedron* C,
 915                                 unsigned MaxRays);
 916 extern Enumeration *Polyhedron_Enumerate(Polyhedron *P,
 917             Polyhedron *C, unsigned MAXRAYS, char **pname);
 918 \end{verbatim}
 919 The argument \verb+MaxRays+ has the same meaning as the argument
 920 \verb+NbMaxCons+ above.
 921 The argument \verb+P+ refers to the $(d+n)$-dimensional
 922 polyhedron defining the parametric polytope.
 923 The argument \verb+C+ is an $n$-dimensional polyhedron containing
 924 extra constraints on the parameter space.
 925 Its primary use is to indicate how many of the dimensions
 926 in \verb+P+ refer to parameters as any constraint in \verb+C+
 927 could equally well have been added to \verb+P+ itself.
 928 Note that the dimensions referring to the parameters should
 929 appear {\em last}.
 930 If either \verb+P+ or \verb+C+ is a union,
 931 then only the first set in the union will be taken into account.
 932 The result is a newly allocated \ai[\tt]{Enumeration}.
 933 As an alternative we also provide a function
 934 (\ai[\tt]{barvinok\_enumerate\_ev} or
 935 \ai[\tt]{barvinok\_enumerate\_with\_options}) that returns
 936 an \ai[\tt]{evalue}.
 937 \begin{verbatim}
 938 evalue* barvinok_enumerate_ev(Polyhedron *P, Polyhedron* C,
 939                               unsigned MaxRays);
 940 evalue* barvinok_enumerate_with_options(Polyhedron *P,
 941         Polyhedron* C, struct barvinok_options *options);
 942 \end{verbatim}
 943
 944 For enumerating parametric sets with existentially quantified variables,
 945 we provide three functions:
 946 \ai[\tt]{barvinok\_enumerate\_e},
 947 \ai[\tt]{barvinok\_enumerate\_pip}
 948 and
 949 \ai[\tt]{barvinok\_enumerate\_isl}.
 950 \begin{verbatim}
 951 evalue* barvinok_enumerate_e(Polyhedron *P,
 952           unsigned exist, unsigned nparam, unsigned MaxRays);
 953 evalue* barvinok_enumerate_e_with_options(Polyhedron *P,
 954           unsigned exist, unsigned nparam,
 955           struct barvinok_options *options);
 956 evalue *barvinok_enumerate_pip(Polyhedron *P,
 957           unsigned exist, unsigned nparam, unsigned MaxRays);
 958 evalue* barvinok_enumerate_pip_with_options(Polyhedron *P,
 959           unsigned exist, unsigned nparam,
 960           struct barvinok_options *options);
 961 evalue *barvinok_enumerate_isl(Polyhedron *P,
 962           unsigned exist, unsigned nparam,
 963           struct barvinok_options *options);
 964 evalue *barvinok_enumerate_scarf(Polyhedron *P,
 965           unsigned exist, unsigned nparam,
 966           struct barvinok_options *options);
 967 \end{verbatim}
 968 The first function tries the simplification rules from
 969 \citeN[Section~4.6.2]{Verdoolaege2005PhD} before resorting to the method
 970 based on \indac{PIP} from \citeN[Section~4.6.3]{Verdoolaege2005PhD}.
 971 The second function immediately applies the technique from
 972 \citeN[Section~4.6.3]{Verdoolaege2005PhD}.
 973 The argument \verb+exist+ refers to the number of existential variables,
 974 whereas
 975 the argument \verb+nparam+ refers to the number of parameters.
 976 The order of the dimensions in \verb+P+ is:
 977 counted variables first, then existential variables and finally
 978 the parameters.
 979 The function \ai[\tt]{barvinok\_enumerate\_scarf} performs the same
 980 computation as the function \ai[\tt]{barvinok\_enumerate\_scarf\_series}
 981 below, but produces an explicit representation instead of a generating function.
 982
 983 \begin{verbatim}
 984 gen_fun * barvinok_series(Polyhedron *P, Polyhedron* C,
 985                           unsigned MaxRays);
 986 gen_fun * barvinok_series_with_options(Polyhedron *P,
 987     Polyhedron* C, barvinok_options *options);
 988 gen_fun *barvinok_enumerate_e_series(Polyhedron *P,
 989                   unsigned exist, unsigned nparam,
 990                   barvinok_options *options);
 991 gen_fun *barvinok_enumerate_scarf_series(Polyhedron *P,
 992                           unsigned exist, unsigned nparam,
 993                           barvinok_options *options);
 994 \end{verbatim}
 995 The function
 996 \ai[\tt]{barvinok\_series} or
 997 \ai[\tt]{barvinok\_series\_with\_options} enumerates parametric polytopes
 998 in the form of a \rgf/.
 999 The polyhedron \verb+P+ is assumed to have only
1000 revlex-positive rays.
1001 \\
1002 The function \ai[\tt]{barvinok\_enumerate\_e\_series} computes a
1003 generating function for the number of point in the parametric set
1004 defined by \verb+P+ with \verb+exist+ existentially quantified
1005 variables using the \ai{projection theorem}, as explained
1006 in \autoref{s:projection}.
1007 The function \ai[\tt]{barvinok\_enumerate\_scarf\_series} computes a
1008 generating function for the number of point in the parametric set
1009 defined by \verb+P+ with \verb+exist+ existentially quantified
1010 variables, which is assumed to be 2.
1011 This function implements the technique of
1012 \shortciteN{Scarf2006Neighborhood} using the \ai{neighborhood complex}
1013 description of \shortciteN{Scarf1981indivisibilities:II}.
1014 It is currently restricted to problems with 3 or 4 constraints involving
1015 the existentially quantified variables.
1016
1017 \subsection{Auxiliary Functions}
1018
1019 In this section we briefly mention some auxiliary functions
1020 available in the \barvinok/ library.
1021
1022 \begin{verbatim}
1023 void Polyhedron_Polarize(Polyhedron *P);
1024 \end{verbatim}
1025 The function \ai[\tt]{Polyhedron\_Polarize}
1026 polarizes its argument and is explained
1027 in \citeN[Section~4.4.2]{Verdoolaege2005PhD}.
1028
1029 \begin{verbatim}
1030 int unimodular_complete(Matrix *M, int row);
1031 \end{verbatim}
1032 The function \ai[\tt]{unimodular\_complete} extends
1033 the first \verb+row+ rows of
1034 \verb+M+ with an integral basis of the orthogonal complement
1035 as explained in Section~\ref{s:completion}.
1036 Returns non-zero
1037 if the resulting matrix is unimodular\index{unimodular matrix}.
1038
1039 \begin{verbatim}
1040 int DomainIncludes(Polyhedron *D1, Polyhedron *D2);
1041 \end{verbatim}
1042 The function \ai[\tt]{DomainIncludes} extends
1043 the function \ai[\tt]{PolyhedronIncludes}
1044 provided by \PolyLib/
1045 to unions of polyhedra.
1046 It checks whether every polyhedron in the union {\tt D2}
1047 is included in some polyhedron of {\tt D1}.
1048
1049 \begin{verbatim}
1050 Polyhedron *DomainConstraintSimplify(Polyhedron *P,
1051                                      unsigned MaxRays);
1052 \end{verbatim}
1053 The value returned by
1054 \ai[\tt]{DomainConstraintSimplify} is a pointer to
1055 a newly allocated \ai[\tt]{Polyhedron} that contains the
1056 same integer points as its first argument but possibly
1057 has simpler constraints.
1058 Each constraint $ g \sp a x \ge c $
1059 is replaced by $ \sp a x \ge \ceil{ \frac c g } $,
1060 where $g$ is the \ac{gcd} of the coefficients in the original
1061 constraint.
1062 The \ai[\tt]{Polyhedron} pointed to by \verb+P+ is destroyed.
1063
1064 \begin{verbatim}
1065 Polyhedron* Polyhedron_Project(Polyhedron *P, int dim);
1066 \end{verbatim}
1067 The function \ai[\tt]{Polyhedron\_Project} projects
1068 \verb+P+ onto its last \verb+dim+ dimensions.
1069
1070 \begin{verbatim}
1071 Matrix *left_inverse(Matrix *M, Matrix **Eq);
1072 \end{verbatim}
1073 The \ai[\tt]{left\_inverse} function computes the left inverse
1074 of \verb+M+ as explained in Section~\ref{s:inverse}.
1075
1076 \sindex{reduced}{basis}
1077 \sindex{generalized}{reduced basis}
1078 \begin{verbatim}
1079 Matrix *Polyhedron_Reduced_Basis(Polyhedron *P,
1080                                  struct barvinok_options *options);
1081 \end{verbatim}
1082 \ai[\tt]{Polyhedron\_Reduced\_Basis} computes
1083 a \ai{generalized reduced basis} of {\tt P}, which
1084 is assumed to be a polytope, using the algorithm
1085 of~\shortciteN{Cook1993implementation}.
1086 See \autoref{s:feasibility} for more information.
1087 The basis vectors are stored in the rows of the matrix returned.
1088
1089 \begin{verbatim}
1090 Vector *Polyhedron_Sample(Polyhedron *P,
1091                           struct barvinok_options *options);
1092 \end{verbatim}
1093 \ai[\tt]{Polyhedron\_Sample} returns an \ai{integer point} of {\tt P}
1094 or {\tt NULL} if {\tt P} contains no integer points.
1095 The integer point is found using the algorithm
1096 of~\shortciteN{Cook1993implementation} and uses
1097 \ai[\tt]{Polyhedron\_Reduced\_Basis} to compute the reduced bases.
1098 See \autoref{s:feasibility} for more information.
1099
1100 \subsection{\protect\ai[\tt]{bernstein} Data Structures and Functions}
1101
1102 The \bernstein/ library used \ai[\tt]{GiNaC} data structures to
1103 represent the data it manipulates.
1104 In particular, a polynomial is stored in a \ai[\tt]{GiNaC::ex},
1105 a list of variable or parameter names is stored in a \ai[\tt]{GiNaC::exvector},
1106 while the parametric vertices or generators are stored in a \ai[\tt]{GiNaC::matrix},
1107 where the rows refer to the generators and the columns to the coordinates
1108 of each generator.
1109
1110 \begin{verbatim}
1111 namespace bernstein {
1112 GiNaC::exvector constructParameterVector(
1113     const char * const *param_names, unsigned nbParams);
1114 GiNaC::exvector constructVariableVector(unsigned nbVariables,
1115                                         const char *prefix);
1116 }
1117 \end{verbatim}
1118 The functions \ai[\tt]{constructParameterVector}
1119 and \ai[\tt]{constructVariableVector} construct a list of variable
1120 names either from a list of {\tt char *}s or
1121 by suffixing {\tt prefix} with a number starting from 0.
1122 Such lists are needed for the functions
1123 \ai[\tt]{domainVertices}, \ai[\tt]{bernsteinExpansion}
1124 and \ai[\tt]{evalue\_bernstein\_coefficients}.
1125
1126 \begin{verbatim}
1127 namespace bernstein {
1128 GiNaC::matrix domainVertices(Param_Polyhedron *PP, Param_Domain *Q,
1129                              const GiNaC::exvector& params);
1130 }
1131 \end{verbatim}
1132 The function \ai[\tt]{domainVertices} constructs a matrix representing the
1133 generators (in this case vertices) of the \ai[\tt]{Param\_Polyhedron} {\tt PP}
1134 for the \ai[\tt]{Param\_Domain} {\tt Q}, to be used
1135 in a call to \ai[\tt]{bernsteinExpansion}.
1136 The elements of {\tt params} are used in the resulting matrix
1137 to refer to the parameters.
1138
1139 \begin{verbatim}
1140 namespace bernstein {
1141 GiNaC::lst bernsteinExpansion(const GiNaC::matrix& vert,
1142                               const GiNaC::ex& poly,
1143                               const GiNaC::exvector& vars,
1144                               const GiNaC::exvector& params);
1145 }
1146 \end{verbatim}
1147 The function \ai[\tt]{bernsteinExpansion} computes the
1148 \ai{Bernstein coefficient}s of the polynomial \verb+poly+
1149 over the \ai{parametric polytope} that is the \ai{convex hull}
1150 of the rows in \verb+vert+.  The vectors \verb+vars+
1151 and \verb+params+ identify the variables (i.e., the coordinates
1152 of the space in which the parametric polytope lives) and
1153 the parameters, respectively.
1154
1155 \begin{verbatim}
1156 namespace bernstein {
1157
1158 typedef std::pair< Polyhedron *, GiNaC::lst > guarded_lst;
1159
1160 struct piecewise_lst {
1161     const GiNaC::exvector vars;
1162     std::vector<guarded_lst> list;
1163     /*  0: just collect terms
1164      *  1: remove obviously smaller terms (maximize)
1165      * -1: remove obviously bigger terms (minimize)
1166      */
1167     int sign;
1168
1169     piecewise_lst(const GiNaC::exvector& vars);
1170     piecewise_lst& combine(const piecewise_lst& other);
1171     void maximize();
1172     void simplify_domains(Polyhedron *ctx, unsigned MaxRays);
1173     GiNaC::numeric evaluate(const GiNaC::exvector& values);
1174     void add(const GiNaC::ex& poly);
1175 }
1176
1177 }
1178 \end{verbatim}
1179 A \ai[\tt]{piecewise\_list} structure represents a list of (disjoint)
1180 polyhedral domains, each with an associated \ai[\tt]{GiNaC::lst}
1181 of polynomials.
1182 The \ai[\tt]{vars} member contains the variable names of the
1183 dimensions of the polyhedral domains.
1184 \\
1185 \ai[\tt]{piecewise\_lst::combine} computes the \ai{common refinement}
1186 of the polyhedral domains in \verb+this+ and \verb+other+ and associates
1187 to each of the resulting subdomains the union of the sets of polynomials
1188 associated to the domains from \verb+this+ and \verb+other+ that contain
1189 the subdomain.
1190 If the \verb+sign+s of the \ai[\tt]{piecewise\_list}s are not zero,
1191 then the (obviously) redundant elements of these sets are removed
1192 from the union.
1193 The result is stored in \verb+this+.
1194 \\
1195 \ai[\tt]{piecewise\_lst::maximize} removes polynomials from domains that evaluate
1196 to a value that is smaller than or equal to the value of some
1197 other polynomial associated to the same domain for each point in the domain.
1198 \\
1199 \ai[\tt]{piecewise\_lst::evaluate} ``evaluates'' the \ai[\tt]{piecewise\_list}
1200 by looking for the domain (if any) that contains the point given by
1201 \verb+values+ and computing the maximal value attained by any of the
1202 associated polynomials evaluated at that point.
1203 \\
1204 \ai[\tt]{piecewise\_lst::add} adds the polynomial \verb+poly+
1205 to each of the polynomial associated to each of the domains.
1206 \\
1207 \ai[\tt]{piecewise\_lst::simplify\_domains} ``simplifies'' the domains
1208 by removing the constraints that are implied by the constraints
1209 in \verb+ctx+, basically by calling \PolyLib/'s
1210 \ai[\tt]{DomainSimplify}.  Note that you should only do this
1211 at the end of your computation.  In particular, you do not
1212 want to call this method before calling
1213 \ai[\tt]{piecewise\_lst::maximize}, since this method will then
1214 have less information on the domains to exploit.
1215
1216
1217 \begin{verbatim}
1218 namespace barvinok {
1219 bernstein::piecewise_lst *evalue_bernstein_coefficients(
1220             bernstein::piecewise_lst *pl_all, evalue *e,
1221             Polyhedron *ctx, const GiNaC::exvector& params);
1222 bernstein::piecewise_lst *evalue_bernstein_coefficients(
1223             bernstein::piecewise_lst *pl_all, evalue *e,
1224             Polyhedron *ctx, const GiNaC::exvector& params,
1225             barvinok_options *options);
1226 }
1227 \end{verbatim}
1228 The \ai[\tt]{evalue\_bernstein\_coefficients} function will compute the
1229 \ai{Bernstein coefficient}s of the piecewise parametric polynomial stored in the
1230 \ai[\tt]{evalue} \verb+e+.
1231 The \verb+params+ vector specifies the names to be used for the parameters,
1232 while the context \ai[\tt]{Polyhedron} \verb+ctx+ specifies extra constraints
1233 on the parameters.
1234 The dimension of \verb+ctx+ needs to be the same as the length of \verb+params+.
1235 The \ai[\tt]{evalue} \verb+e+ is assumed to be of type \ai[\tt]{partition}
1236 and each of the domains in this \ai[\tt]{partition} is interpreted
1237 as a parametric polytope in the given parameters. The procedure
1238 will compute the \ai{Bernstein coefficient}s of the associated polynomial
1239 over each such parametric polytope.
1240 The resulting \ai[\tt]{bernstein::piecewise\_lst} collects the
1241 Bernstein coefficients over all parametric polytopes in \verb+e+.
1242 If \verb+pl_all+ is not \verb+NULL+ then this list will be combined
1243 with the list computed by calling \ai[\tt]{piecewise\_lst::combine}.
1244 If \ai[\tt]{bernstein\_optimize} is set to \ai[\tt]{BV\_BERNSTEIN\_MAX}
1245 in \verb+options+, then this combination will remove obviously
1246 redundant Bernstein coefficients with respect to upper bound computation
1247 and similarly for \ai[\tt]{BV\_BERNSTEIN\_MIN}.
1248 The default (\ai[\tt]{BV\_BERNSTEIN\_NONE}) is to only remove duplicate
1249 Bernstein coefficients.