1 \section{Internal Representation of the
\protect\ai[\tt]{barvinok
} library
}
3 Our
\barvinok/ library is built on top of
\PolyLib/
4 \shortcite{Wilde1993,Loechner1999
}.
5 In particular, it reuses the implementations
7 \shortciteN{Loechner97parameterized
}
8 for computing parametric vertices
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.
18 \subsection{Existing Data Structures
}
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.
29 The basic structure for representing (unions of) polyhedra is a
32 typedef struct polyhedron
{
33 unsigned Dimension, NbConstraints, NbRays, NbEq, NbBid;
38 struct polyhedron *next;
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
}.
71 Quasi-polynomials are represented using the
72 \ai[\tt]{evalue
} and
\ai[\tt]{enode
} structures.
74 typedef enum
{ polynomial, periodic, evector
} enode_type;
76 typedef struct _evalue
{
77 Value d; /* denominator */
79 Value n; /* numerator (if denominator !=
0) */
80 struct _enode *p; /* pointer (if denominator ==
0) */
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 */
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
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
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
111 \verb+arr
[0]+ +
\verb+arr
[1]+ p +
\verb+arr
[2]+ p^
2 +
\cdots +
112 \verb+arr
[l-
1]+ p^
{l-
1}
115 If it is a periodic, then it represents
118 \verb+arr
[0]+,
\verb+arr
[1]+,
\verb+arr
[2]+,
\ldots,
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.
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 */
139 For more information on these structures, we refer to
\shortciteN{Loechner1999
}.
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
147 [1,
2]_p p^
2 +
3 p +
\frac 5 2
154 \begin{tabular
}{|c|c|c|
}
156 \multicolumn{2}{|c|
}{type
} & polynomial \\
158 \multicolumn{2}{|c|
}{size
} &
3 \\
160 \multicolumn{2}{|c|
}{pos
} &
1 \\
162 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
2 \\
166 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
170 \smash{\lower 6.25pt
\hbox{arr
[2]}} & d &
0 \\
177 +DR*!DR
\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial
}\hskip 1.5\tabcolsep}+C="a"
178 \POS(
60,-
15)*!UL
{\hbox{
180 \begin{tabular
}{|c|c|c|
}
182 \multicolumn{2}{|c|
}{type
} & periodic \\
184 \multicolumn{2}{|c|
}{size
} &
2 \\
186 \multicolumn{2}{|c|
}{pos
} &
1 \\
188 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
1 \\
192 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
199 +UL+<
0.5\tabcolsep,
0pt>*!UL
\hbox{\strut}+CL="b"
201 \POS"box1"+UC*++!D
\hbox{\tt enode
}
202 \POS"box2"+UC*++!D
\hbox{\tt enode
}
204 \caption{The quasi-polynomial $
[1,
2]_p p^
2 +
3 p +
\frac 5 2$.
}
209 \subsection{Data Structures for Quasi-polynomials
}
212 Internally, we do not represent our quasi-polynomials
213 as step-polynomials, but, similarly to
\shortciteN{Loechner1999
},
214 as polynomials with periodic numbers for coefficients.
215 However, we also allow our periodic numbers to be represented by
216 fractional parts of degree-$
1$ polynomials rather than
217 an explicit enumeration using the
\ai[\tt]{periodic
} type.
218 By default, the current version of
\barvinok/ uses
219 \ai[\tt]{periodic
}s, but this can be changed through
220 the
\ai[\tt]{--enable-fractional
} configure option.
221 In the latter case, the quasi-polynomial using fractional
222 parts can also be converted to an actual step-polynomial
223 using
\ai[\tt]{evalue
\_frac2floor}, but this is not fully
226 For reasons of compatibility,
%
227 \footnote{Also known as laziness.
}
228 we shoehorned our representations for piecewise quasi-polynomials
229 into the existing data structures.
230 To this effect, we introduced four new types,
231 \ai[\tt]{fractional
},
\ai[\tt]{relation
},
232 \ai[\tt]{partition
} and
\ai[\tt]{flooring
}.
234 typedef enum
{ polynomial, periodic, evector, fractional,
235 relation, partition, flooring
} enode_type;
237 The field
\ai[\tt]{pos
} is not used in most of these
238 additional types and is therefore set to
\verb+-
1+.
240 The types
\ai[\tt]{fractional
} and
\ai[\tt]{flooring
}
241 represent polynomial expressions in a fractional part or a floor respectively.
242 The generator is stored in
\verb+arr
[0]+, while the
243 coefficients are stored in the remaining array elements.
244 That is, an
\ai[\tt]{enode
} of type
\ai[\tt]{fractional
}
247 \verb+arr
[1]+ +
\verb+arr
[2]+ \
{\verb+arr
[0]+\
} +
248 \verb+arr
[3]+ \
{\verb+arr
[0]+\
}^
2 +
\cdots +
249 \verb+arr
[l-
1]+ \
{\verb+arr
[0]+\
}^
{l-
2}
252 An
\ai[\tt]{enode
} of type
\ai[\tt]{flooring
}
255 \verb+arr
[1]+ +
\verb+arr
[2]+
\lfloor\verb+arr
[0]+
\rfloor +
256 \verb+arr
[3]+
\lfloor\verb+arr
[0]+
\rfloor^
2 +
\cdots +
257 \verb+arr
[l-
1]+
\lfloor\verb+arr
[0]+
\rfloor^
{l-
2}
262 The internal representation of the quasi-polynomial
263 $$
\left(
1+
2 \left\
{\frac p
2\right\
}\right) p^
2 +
3 p +
\frac 5 2$$
264 is shown in Figure~
\ref{f:fractional
}.
270 \begin{tabular
}{|c|c|c|
}
272 \multicolumn{2}{|c|
}{type
} & polynomial \\
274 \multicolumn{2}{|c|
}{size
} &
3 \\
276 \multicolumn{2}{|c|
}{pos
} &
1 \\
278 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
2 \\
282 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
286 \smash{\lower 6.25pt
\hbox{arr
[2]}} & d &
0 \\
293 +DR*!DR
\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial
}\hskip 1.5\tabcolsep}+C="a"
294 \POS(
60,
0)*!UL
{\hbox{
296 \begin{tabular
}{|c|c|c|
}
298 \multicolumn{2}{|c|
}{type
} & fractional \\
300 \multicolumn{2}{|c|
}{size
} &
3 \\
302 \multicolumn{2}{|c|
}{pos
} & -
1 \\
304 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
0 \\
308 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
312 \smash{\lower 6.25pt
\hbox{arr
[2]}} & d &
1 \\
319 +UL+<
0.5\tabcolsep,
0pt>*!UL
\hbox{\strut}+CL="b"
321 \POS"box2"+UR*!UR
{\hbox{
335 }+CD*!U
{\strut}+C="c"
336 \POS(
60,-
50)*!UL
{\hbox{
338 \begin{tabular
}{|c|c|c|
}
340 \multicolumn{2}{|c|
}{type
} & polynomial \\
342 \multicolumn{2}{|c|
}{size
} &
2 \\
344 \multicolumn{2}{|c|
}{pos
} &
1 \\
346 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
1 \\
350 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
2 \\
357 +UR-<
0.8\tabcolsep,
0pt>*!UR
\hbox{\strut}+CR="d"
359 \POS"box1"+UC*++!D
\hbox{\tt enode
}
360 \POS"box2"+UC*++!D
\hbox{\tt enode
}
361 \POS"box3"+UC*++!D
\hbox{\tt enode
}
363 \caption{The quasi-polynomial
364 $
\left(
1+
2 \left\
{\frac p
2\right\
}\right) p^
2 +
3 p +
\frac 5 2$.
}
370 The
\ai[\tt]{relation
} type is used to represent
\ai{stride
}s.
371 In particular, if the value of
\ai[\tt]{size
} is
2, then
372 the value of a
\ai[\tt]{relation
} is (in pseudo-code):
374 (value(arr
[0]) ==
0) ? value(arr
[1]) :
0
376 If the size is
3, then the value is:
378 (value(arr
[0]) ==
0) ? value(arr
[1]) : value(arr
[2])
380 The type of
\verb+arr
[0]+ is typically
\ai[\tt]{fractional
}.
382 Finally, the
\ai[\tt]{partition
} type is used to
383 represent piecewise quasi-polynomials.
384 We prefer to encode this information inside
\ai[\tt]{evalue
}s
386 rather than using
\ai[\tt]{Enumeration
}s since we want
387 to perform the same kinds of operations on both quasi-polynomials
388 and piecewise quasi-polynomials.
389 An
\ai[\tt]{enode
} of type
\ai[\tt]{partition
} may not be nested
390 inside another
\ai[\tt]{enode
}.
391 The size of the array is twice the number of ``chambers''.
392 Pointers to chambers are stored in the even slots,
393 whereas pointer to the associated quasi-polynomials
394 are stored in the odd slots.
395 To be able to store pointers to chambers, the
396 definition of
\ai[\tt]{evalue
} was changed as follows.
398 typedef struct _evalue
{
399 Value d; /* denominator */
401 Value n; /* numerator (if denominator >
0) */
402 struct _enode *p; /* pointer (if denominator ==
0) */
403 Polyhedron *D; /* domain (if denominator == -
1) */
407 Note that we allow a ``chamber'' to be a union of polyhedra
408 as discussed in
\citeN[Section~
4.5.1]{Verdoolaege2005PhD
}.
409 Chambers with extra variables, i.e., those of
410 \citeN[Section~
4.6.5]{Verdoolaege2005PhD
},
411 are only partially supported.
412 The field
\ai[\tt]{pos
} is set to the actual dimension,
413 i.e., the number of parameters.
415 \subsection{Operations on Quasi-polynomials
}
418 In this section we discuss some of the more important
419 operations on
\ai[\tt]{evalue
}s provided by the
421 Some of these operations are extensions
422 of the functions from
\PolyLib/ with the same name.
425 void eadd(evalue *e1,evalue *res);
426 void emul (evalue *e1, evalue *res );
428 The functions
\ai[\tt]{eadd
} and
\ai[\tt]{emul
} takes
429 two (pointers to)
\ai[\tt]{evalue
}s
\verb+e1+ and
\verb+res+
430 and computes their sum and product respectively.
431 The result is stored in
\verb+res+, overwriting (and deallocating)
432 the original value of
\verb+res+.
433 It is an error if exactly one of
434 the arguments of
\ai[\tt]{eadd
} is of type
\ai[\tt]{partition
}
435 (unless the other argument is
\verb+
0+).
436 The addition and multiplication operations are described
437 in
\citeN[Section~
4.5.1]{Verdoolaege2005PhD
}
438 and~
\citeN[Section~
4.5.2]{Verdoolaege2005PhD
}
441 The function
\ai[\tt]{eadd
} is an extension of the function
442 \ai[\tt]{new
\_eadd} from
\shortciteN{Seghir2002
}.
443 Apart from supporting the additional types from Section~
\ref{a:data
},
444 the new version also additionally imposes an order on the nesting of
445 different
\ai[\tt]{enode
}s.
446 Without such an ordering,
\ai[\tt]{evalue
}s could be constructed
447 representing for example
449 (
0 y^
0 + (
0 x^
0 +
1 x^
1 ) y^
1 ) x^
0 + (
0 y^
0 -
1 y^
1) x^
1
452 which is just a funny way of saying $
0$.
455 void eor(evalue *e1, evalue *res);
457 The function
\ai[\tt]{eor
} implements the
\ai{union
}
458 operation from
\citeN[Section~
4.5.3]{Verdoolaege2005PhD
}. Both arguments
459 are assumed to correspond to indicator functions.
462 evalue *esum(evalue *E, int nvar);
464 The function
\ai[\tt]{esum
} performs the summation
465 operation from
\citeN[Section~
4.5.4]{Verdoolaege2005PhD
}.
466 The piecewise step-polynomial represented by
\verb+E+ is summated
467 over its first
\verb+nvar+ variables.
468 Note that
\verb+E+ must be zero or of type
\ai[\tt]{partition
}.
469 The function returns the result in a newly allocated
471 Note also that
\verb+E+ needs to have been converted
472 from
\ai[\tt]{fractional
}s to
\ai[\tt]{flooring
}s using
473 the function
\ai[\tt]{evalue
\_frac2floor}.
475 void evalue_frac2floor(evalue *e);
477 This function also ensures that the arguments of the
478 \ai[\tt]{flooring
}s are positive in the relevant chambers.
479 It currently assumes that the argument of each
480 \ai[\tt]{fractional
} in the original
\ai[\tt]{evalue
}
481 has a minimum in the corresponding chamber.
484 double compute_evalue(evalue *e,Value *list_args);
485 Value *compute_poly(Enumeration *en,Value *list_args);
487 The functions
\ai[\tt]{compute
\_evalue} and
488 \ai[\tt]{compute
\_poly} evaluate a (piecewise) quasi-polynomial
489 at a certain point. The argument
\verb+list_args+
490 points to an array of
\ai[\tt]{Value
}s that is assumed
492 The
\verb+double+ return value of
\ai[\tt]{compute
\_evalue}
493 is inherited from
\PolyLib/.
496 void print_evalue(FILE *DST,evalue *e,char **pname);
498 The function
\ai[\tt]{print
\_evalue} dumps a human-readable
499 representation to the stream pointed to by
\verb+DST+.
500 The argument
\verb+pname+ points
501 to an array of character strings representing the parameter names.
502 The array is assumed to be long enough.
505 int eequal(evalue *e1,evalue *e2);
507 The function
\ai[\tt]{eequal
} return true (
\verb+
1+) if its
508 two arguments are structurally identical.
509 I.e., it does
{\em not\/
} check whether the two
510 (piecewise) quasi-polynomial represent the same function.
513 void reduce_evalue (evalue *e);
515 The function
\ai[\tt]{reduce
\_evalue} performs some
516 simplifications on
\ai[\tt]{evalue
}s.
517 Here, we only describe the simplifications that are directly
518 related to the internal representation.
519 Some other simplifications are explained in
520 \citeN[Section~
4.7.2]{Verdoolaege2005PhD
}.
521 If the highest order coefficients of a
\ai[\tt]{polynomial
},
522 \ai[\tt]{fractional
} or
\ai[\tt]{flooring
} are zero (possibly
523 after some other simplifications), then the size of the array
524 is reduced. If only the constant term remains, i.e.,
525 the size is reduced to $
1$ for
\ai[\tt]{polynomial
} or to $
2$
526 for the other types, then the whole node is replaced by
528 Additionally, if the argument of a
\ai[\tt]{fractional
}
529 has been reduced to a constant, then the whole node
530 is replaced by its partial evaluation.
531 A
\ai[\tt]{relation
} is similarly reduced if its second
532 branch or both its branches are zero.
533 Chambers with zero associated quasi-polynomials are
534 discarded from a
\ai[\tt]{partition
}.
536 \subsection{Generating Functions
}
538 The representation of
\rgf/s uses
539 some basic types from the
\ai[\tt]{NTL
} library
\shortcite{NTL
}
540 for representing arbitrary precision integers
542 as well as vectors (
\ai[\tt]{vec
\_ZZ}) and matrices (
\ai[\tt]{mat
\_ZZ})
544 Each term in a
\rgf/ is represented by a
\ai[\tt]{short
\_rat}
549 /* rows: terms in numerator */
554 /* rows: factors in denominator */
559 The fields
\ai[\tt]{n
} and
\ai[\tt]{d
} represent the
560 numerator and the denominator respectively.
561 Note that in our implementation we combine terms
562 with the same denominator.
563 In the numerator, each row of
\ai[\tt]{coeff
} and
\ai[\tt]{power
}
564 represents a single such term.
565 The matrix
\ai[\tt]{coeff
} has two columns, one for the
566 numerator and one for the denominator of the rational coefficient
567 $
\alpha_i$ of each term.
568 The columns of
\ai[\tt]{power
} correspond to the powers
570 In the denominator, each row of
\ai[\tt]{power
}
571 corresponds to the power $
\vec b_
{ij
}$ of a
572 factor in the denominator.
576 shows the internal representation of
578 \frac{\frac 3 2 \, x_0^
2 x_1^
3 +
2 \, x_0^
5 x_1^
{-
7}}
579 { (
1 - x_0 x_1^
{-
3}) (
1 - x_1^
2)
}
585 \begin{minipage
}{0cm
}
589 \begin{tabular
}{|c|c|c|
}
604 }+UC*++!D
\hbox{\tt short
\_rat}
608 \caption{Representation of
610 \left(
\frac 3 2 \, x_0^
2 x_1^
3 +
2 \, x_0^
5 x_1^
{-
7}\right)
611 /
\left( (
1 - x_0 x_1^
{-
3}) (
1 - x_1^
2)
\right)
618 The whole
\rgf/ is represented by a
\ai[\tt]{gen
\_fun}
622 std::vector< short_rat * > term;
625 void add(ZZ& cn, ZZ& cd, vec_ZZ& num, mat_ZZ& den);
626 void print(unsigned int nparam, char **param_name);
629 gen_fun(Polyhedron *C = NULL) : context(C)
{}
633 The method
\ai[\tt]{gen
\_fun::add
} adds a new term to the
\rgf/.
634 It makes all powers in the denominator lexico-positive,
635 orders them in lexicographical order and inserts the new
636 term in
\ai[\tt]{term
} according to the lexicographical
637 order of the combined powers in the denominator.
638 The method
\ai[\tt]{gen
\_fun::operator evalue *
} performs
639 the conversion from
\rgf/ to
\psp/ explained in
640 \citeN[Section~
4.5.5]{Verdoolaege2005PhD
}.
641 The
\ai[\tt]{Polyhedron
} \ai[\tt]{context
} is the superset
642 of all points where the enumerator is non-zero used during this conversion,
643 i.e., it is the set $Q$ from
\citeN[Equation~
4.31]{Verdoolaege2005PhD
}.
644 If
\ai[\tt]{context
} is
\verb+NULL+ the maximal
645 allowed context is assumed, i.e., the maximal
646 region with lexico-positive rays.
648 \subsection{Counting Functions
}
649 \label{a:counting:functions
}
651 Our library provides essentially three different counting functions:
652 one for non-parametric polytopes, one for parametric polytopes
653 and one for parametric sets with existential variables.
656 void barvinok_count(Polyhedron *P, Value* result,
659 The function
\ai[\tt]{barvinok
\_count} enumerates the non-parametric
660 polytope
\verb+P+ and returns the result in the
\ai[\tt]{Value
}
661 pointed to by
\verb+result+, which needs to have been allocated
663 The argument
\verb+NbMaxCons+ is passed to various
\PolyLib/
664 functions and defines the
665 maximum size of a table used in the double description computation
666 in the
\PolyLib/ function
\ai[\tt]{Chernikova
}.
667 In earlier versions of
\PolyLib/,
668 this parameter had to be conservatively set
669 to a high number to ensure successful operation,
670 resulting in significant memory overhead.
671 Our change to allow this table to grow
672 dynamically is available in recent versions of
\PolyLib/.
673 In these versions, the value no longer indicates the maximal
674 table size, but rather the size of the initial allocation.
675 This value may be set to
\verb+
0+.
677 The function
\ai[\tt]{barvinok
\_enumerate} for enumerating
678 parametric polytopes was meant to be
679 a drop-in replacement of
\PolyLib/'s
\ai[\tt]{Polyhedron
\_Enumerate}
681 Unfortunately, the latter has been changed to
682 accept an extra argument in recent versions of
\PolyLib/ as shown below.
684 Enumeration* barvinok_enumerate(Polyhedron *P, Polyhedron* C,
686 extern Enumeration *Polyhedron_Enumerate(Polyhedron *P,
687 Polyhedron *C, unsigned MAXRAYS, char **pname);
689 The argument
\verb+MaxRays+ has the same meaning as the argument
690 \verb+NbMaxCons+ above.
691 The argument
\verb+P+ refers to the $(d+n)$-dimensional
692 polyhedron defining the parametric polytope.
693 The argument
\verb+C+ is an $n$-dimensional polyhedron containing
694 extra constraints on the parameter space.
695 Its primary use is to indicate how many of the dimensions
696 in
\verb+P+ refer to parameters as any constraint in
\verb+C+
697 could equally well have been added to
\verb+P+ itself.
698 Note that the dimensions referring to the parameters should
700 The result is a newly allocated
\ai[\tt]{Enumeration
}.
701 As an alternative we also provide a function
702 (
\ai[\tt]{barvinok
\_enumerate\_ev}) that returns
705 evalue* barvinok_enumerate_ev(Polyhedron *P, Polyhedron* C,
709 For enumerating parametric sets with existentially quantified variables,
710 we provide two functions:
711 \ai[\tt]{barvinok
\_enumerate\_e}
713 \ai[\tt]{barvinok
\_enumerate\_pip}.
715 evalue* barvinok_enumerate_e(Polyhedron *P,
716 unsigned exist, unsigned nparam, unsigned MaxRays);
717 evalue *barvinok_enumerate_pip(Polyhedron *P,
718 unsigned exist, unsigned nparam, unsigned MaxRays);
720 The first function tries the simplification rules from
721 \citeN[Section~
4.6.2]{Verdoolaege2005PhD
} before resorting to the method
722 based on
\indac{PIP
} from
\citeN[Section~
4.6.3]{Verdoolaege2005PhD
}.
723 The second function immediately applies the technique from
724 \citeN[Section~
4.6.3]{Verdoolaege2005PhD
}.
725 The argument
\verb+exist+ refers to the number of existential variables,
727 the argument
\verb+nparam+ refers to the number of parameters.
728 The order of the dimensions in
\verb+P+ is:
729 counted variables first, then existential variables and finally
733 \ai[\tt]{barvinok
\_series} enumerates parametric polytopes
734 in the form of a
\rgf/.
735 The polyhedron
\verb+P+ is assumed to have only
736 lexico-positive rays.
738 gen_fun * barvinok_series(Polyhedron *P, Polyhedron* C,
742 \subsection{Auxiliary Functions
}
744 In this section we briefly mention some auxiliary functions
745 available in the
\barvinok/ library.
748 void Polyhedron_Polarize(Polyhedron *P);
750 The function
\ai[\tt]{Polyhedron
\_Polarize}
751 polarizes its argument and is explained
752 in
\citeN[Section~
4.4.2]{Verdoolaege2005PhD
}.
755 Matrix * unimodular_complete(Vector *row);
757 The function
\ai[\tt]{unimodular
\_complete} extends
758 \verb+row+ to a
\ai{unimodular matrix
} using the
759 algorithm of
\shortciteN{Bik1996PhD
}.
762 int DomainIncludes(Polyhedron *Pol1, Polyhedron *Pol2);
764 The function
\ai[\tt]{DomainIncludes
} extends
765 the function
\ai[\tt]{PolyhedronIncludes
}
766 provided by
\PolyLib/
767 to unions of polyhedra.
768 It checks whether its first argument is a superset of
772 Polyhedron *DomainConstraintSimplify(Polyhedron *P,
775 The value returned by
776 \ai[\tt]{DomainConstraintSimplify
} is a pointer to
777 a newly allocated
\ai[\tt]{Polyhedron
} that contains the
778 same integer points as its first argument but possibly
779 has simpler constraints.
780 Each constraint $ g
\sp a x
\ge c $
781 is replaced by $
\sp a x
\ge \ceil{ \frac c g
} $,
782 where $g$ is the
\ac{gcd
} of the coefficients in the original
784 The
\ai[\tt]{Polyhedron
} pointed to by
\verb+P+ is destroyed.
787 Polyhedron* Polyhedron_Project(Polyhedron *P, int dim);
789 The function
\ai[\tt]{Polyhedron
\_Project} projects
790 \verb+P+ onto its last
\verb+dim+ dimensions.