1 \section{\protect\PolyLib/ interface of the
\protect\ai[\tt]{barvinok
} library
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.
9 Our
\barvinok/ library is built on top of
\PolyLib/
10 \shortcite{Wilde1993,Loechner1999
}.
11 In particular, it reuses the implementations
13 \shortciteN{Loechner97parameterized
}
14 for computing parametric vertices
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.
24 \subsection{Existing Data Structures
}
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.
35 The basic structure for representing (unions of) polyhedra is a
38 typedef struct polyhedron
{
39 unsigned Dimension, NbConstraints, NbRays, NbEq, NbBid;
44 struct polyhedron *next;
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
}.
77 Quasi-polynomials are represented using the
78 \ai[\tt]{evalue
} and
\ai[\tt]{enode
} structures.
80 typedef enum
{ polynomial, periodic, evector
} enode_type;
82 typedef struct _evalue
{
83 Value d; /* denominator */
85 Value n; /* numerator (if denominator !=
0) */
86 struct _enode *p; /* pointer (if denominator ==
0) */
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 */
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
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
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
117 \verb+arr
[0]+ +
\verb+arr
[1]+ p +
\verb+arr
[2]+ p^
2 +
\cdots +
118 \verb+arr
[l-
1]+ p^
{l-
1}
121 If it is a periodic, then it represents
124 \verb+arr
[0]+,
\verb+arr
[1]+,
\verb+arr
[2]+,
\ldots,
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.
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 */
145 For more information on these structures, we refer to
\shortciteN{Loechner1999
}.
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
153 [1,
2]_p p^
2 +
3 p +
\frac 5 2
160 \begin{tabular
}{|c|c|c|
}
162 \multicolumn{2}{|c|
}{type
} & polynomial \\
164 \multicolumn{2}{|c|
}{size
} &
3 \\
166 \multicolumn{2}{|c|
}{pos
} &
1 \\
168 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
2 \\
172 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
176 \smash{\lower 6.25pt
\hbox{arr
[2]}} & d &
0 \\
183 +DR*!DR
\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial
}\hskip 1.5\tabcolsep}+C="a"
184 \POS(
60,-
15)*!UL
{\hbox{
186 \begin{tabular
}{|c|c|c|
}
188 \multicolumn{2}{|c|
}{type
} & periodic \\
190 \multicolumn{2}{|c|
}{size
} &
2 \\
192 \multicolumn{2}{|c|
}{pos
} &
1 \\
194 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
1 \\
198 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
205 +UL+<
0.5\tabcolsep,
0pt>*!UL
\hbox{\strut}+CL="b"
207 \POS"box1"+UC*++!D
\hbox{\tt enode
}
208 \POS"box2"+UC*++!D
\hbox{\tt enode
}
210 \caption{The quasi-polynomial $
[1,
2]_p p^
2 +
3 p +
\frac 5 2$.
}
218 The
\ai[\tt]{barvinok
\_options} structure contains various
219 options that influence the behavior of the library.
222 struct barvinok_options
{
223 struct barvinok_stats *stats;
225 /* PolyLib options */
229 /* LLL reduction parameter delta=LLL_a/LLL_b */
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;
240 unsigned long max_index;
243 int count_sample_infinite;
245 int try_Delaunay_triangulation;
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)
263 #define BV_VOL_LIFT
0
264 #define BV_VOL_VERTEX
1
265 #define BV_VOL_BARYCENTER
2
266 int volume_triangulate;
268 /* basis reduction options */
269 #define BV_GBR_NONE
0
270 #define BV_GBR_GLPK
1
274 #define BV_LP_POLYLIB
0
281 #define BV_HULL_GBR
0
282 #define BV_HULL_HILBERT
1
286 struct barvinok_options *barvinok_options_new_with_defaults();
289 The function
\ai[\tt]{barvinok
\_options\_new\_with\_defaults}
290 can be used to create a
\ai[\tt]{barvinok
\_options} structure
294 \item \PolyLib/ options
298 \item \ai[\tt]{MaxRays
}
300 The value of
\ai[\tt]{MaxRays
} is passed to various
\PolyLib/
301 functions and defines the
302 maximum size of a table used in the
\ai{double description
} computation
303 in the
\PolyLib/ function
\ai[\tt]{Chernikova
}.
304 In earlier versions of
\PolyLib/,
305 this parameter had to be conservatively set
306 to a high number to ensure successful operation,
307 resulting in significant memory overhead.
308 Our change to allow this table to grow
309 dynamically is available in recent versions of
\PolyLib/.
310 In these versions, the value no longer indicates the maximal
311 table size, but rather the size of the initial allocation.
312 This value may be set to
\verb+
0+ or left as set
313 by
\ai[\tt]{barvinok
\_options\_new\_with\_defaults}.
317 \item \ai[\tt]{NTL
} options
321 \item \ai[\tt]{LLL
\_a}
322 \item \ai[\tt]{LLL
\_b}
324 The values used for the
\ai{reduction parameter
}
325 in the call to
\ai[\tt]{NTL
}'s implementation of
\indac{LLL
}.
329 \item \ai[\tt]{barvinok
} specific options
333 \item \ai[\tt]{incremental
\_specialization}
335 Selects the
\ai{specialization
} algorithm to be used.
336 If set to
{\tt 0} then a direct specialization is performed
337 using a random vector.
338 Value
{\tt 1} selects a depth first incremental specialization,
339 while value
{\tt 2} selects a breadth first incremental specialization.
340 The default is selected by the
\ai[\tt]{--enable-incremental
}
341 \ai[\tt]{configure
} option.
342 For more information we refer to~
\citeN[Section~
4.4.3]{Verdoolaege2005PhD
}.
348 \subsection{Data Structures for Quasi-polynomials
}
351 Internally, we do not represent our
\ai{quasi-polynomial
}s
352 as step-polynomials, but instead as polynomials of
353 fractional parts of degree-$
1$ polynomials.
354 However, we also allow our quasi-polynomials to be represented
355 as polynomials with periodic numbers for coefficients,
356 similarly to
\shortciteN{Loechner1999
}.
357 By default, the current version of
\barvinok/ uses
358 \ai[\tt]{fractional
}s, but this can be changed through
359 the
\ai[\tt]{--disable-fractional
} configure option.
360 When this option is specified, the periodic numbers
362 an explicit enumeration using the
\ai[\tt]{periodic
} type.
363 A quasi-polynomial based on fractional
364 parts can also be converted to an actual step-polynomial
365 using
\ai[\tt]{evalue
\_frac2floor}, but this is not fully
368 For reasons of compatibility,
%
369 \footnote{Also known as laziness.
}
370 we shoehorned our representations for piecewise quasi-polynomials
371 into the existing data structures.
372 To this effect, we introduced four new types,
373 \ai[\tt]{fractional
},
\ai[\tt]{relation
},
374 \ai[\tt]{partition
} and
\ai[\tt]{flooring
}.
376 typedef enum
{ polynomial, periodic, evector, fractional,
377 relation, partition, flooring
} enode_type;
379 The field
\ai[\tt]{pos
} is not used in most of these
380 additional types and is therefore set to
\verb+-
1+.
382 The types
\ai[\tt]{fractional
} and
\ai[\tt]{flooring
}
383 represent polynomial expressions in a fractional part or a floor respectively.
384 The generator is stored in
\verb+arr
[0]+, while the
385 coefficients are stored in the remaining array elements.
386 That is, an
\ai[\tt]{enode
} of type
\ai[\tt]{fractional
}
389 \verb+arr
[1]+ +
\verb+arr
[2]+ \
{\verb+arr
[0]+\
} +
390 \verb+arr
[3]+ \
{\verb+arr
[0]+\
}^
2 +
\cdots +
391 \verb+arr
[l-
1]+ \
{\verb+arr
[0]+\
}^
{l-
2}
394 An
\ai[\tt]{enode
} of type
\ai[\tt]{flooring
}
397 \verb+arr
[1]+ +
\verb+arr
[2]+
\lfloor\verb+arr
[0]+
\rfloor +
398 \verb+arr
[3]+
\lfloor\verb+arr
[0]+
\rfloor^
2 +
\cdots +
399 \verb+arr
[l-
1]+
\lfloor\verb+arr
[0]+
\rfloor^
{l-
2}
404 The internal representation of the quasi-polynomial
405 $$
\left(
1+
2 \left\
{\frac p
2\right\
}\right) p^
2 +
3 p +
\frac 5 2$$
406 is shown in Figure~
\ref{f:fractional
}.
412 \begin{tabular
}{|c|c|c|
}
414 \multicolumn{2}{|c|
}{type
} & polynomial \\
416 \multicolumn{2}{|c|
}{size
} &
3 \\
418 \multicolumn{2}{|c|
}{pos
} &
1 \\
420 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
2 \\
424 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
428 \smash{\lower 6.25pt
\hbox{arr
[2]}} & d &
0 \\
435 +DR*!DR
\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial
}\hskip 1.5\tabcolsep}+C="a"
436 \POS(
60,
0)*!UL
{\hbox{
438 \begin{tabular
}{|c|c|c|
}
440 \multicolumn{2}{|c|
}{type
} & fractional \\
442 \multicolumn{2}{|c|
}{size
} &
3 \\
444 \multicolumn{2}{|c|
}{pos
} & -
1 \\
446 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
0 \\
450 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
1 \\
454 \smash{\lower 6.25pt
\hbox{arr
[2]}} & d &
1 \\
461 +UL+<
0.5\tabcolsep,
0pt>*!UL
\hbox{\strut}+CL="b"
463 \POS"box2"+UR*!UR
{\hbox{
477 }+CD*!U
{\strut}+C="c"
478 \POS(
60,-
50)*!UL
{\hbox{
480 \begin{tabular
}{|c|c|c|
}
482 \multicolumn{2}{|c|
}{type
} & polynomial \\
484 \multicolumn{2}{|c|
}{size
} &
2 \\
486 \multicolumn{2}{|c|
}{pos
} &
1 \\
488 \smash{\lower 6.25pt
\hbox{arr
[0]}} & d &
1 \\
492 \smash{\lower 6.25pt
\hbox{arr
[1]}} & d &
2 \\
499 +UR-<
0.8\tabcolsep,
0pt>*!UR
\hbox{\strut}+CR="d"
501 \POS"box1"+UC*++!D
\hbox{\tt enode
}
502 \POS"box2"+UC*++!D
\hbox{\tt enode
}
503 \POS"box3"+UC*++!D
\hbox{\tt enode
}
505 \caption{The quasi-polynomial
506 $
\left(
1+
2 \left\
{\frac p
2\right\
}\right) p^
2 +
3 p +
\frac 5 2$.
}
512 The
\ai[\tt]{relation
} type is used to represent
\ai{stride
}s.
513 In particular, if the value of
\ai[\tt]{size
} is
2, then
514 the value of a
\ai[\tt]{relation
} is (in pseudo-code):
516 (value(arr
[0]) ==
0) ? value(arr
[1]) :
0
518 If the size is
3, then the value is:
520 (value(arr
[0]) ==
0) ? value(arr
[1]) : value(arr
[2])
522 The type of
\verb+arr
[0]+ is typically
\ai[\tt]{fractional
}.
524 Finally, the
\ai[\tt]{partition
} type is used to
525 represent piecewise quasi-polynomials.
526 We prefer to encode this information inside
\ai[\tt]{evalue
}s
528 rather than using
\ai[\tt]{Enumeration
}s since we want
529 to perform the same kinds of operations on both quasi-polynomials
530 and piecewise quasi-polynomials.
531 An
\ai[\tt]{enode
} of type
\ai[\tt]{partition
} may not be nested
532 inside another
\ai[\tt]{enode
}.
533 The size of the array is twice the number of ``chambers''.
534 Pointers to chambers are stored in the even slots,
535 whereas pointer to the associated quasi-polynomials
536 are stored in the odd slots.
537 To be able to store pointers to chambers, the
538 definition of
\ai[\tt]{evalue
} was changed as follows.
540 typedef struct _evalue
{
541 Value d; /* denominator */
543 Value n; /* numerator (if denominator >
0) */
544 struct _enode *p; /* pointer (if denominator ==
0) */
545 Polyhedron *D; /* domain (if denominator == -
1) */
549 Note that we allow a ``chamber'' to be a union of polyhedra
550 as discussed in
\citeN[Section~
4.5.1]{Verdoolaege2005PhD
}.
551 Chambers with extra variables, i.e., those of
552 \citeN[Section~
4.6.5]{Verdoolaege2005PhD
},
553 are only partially supported.
554 The field
\ai[\tt]{pos
} is set to the actual dimension,
555 i.e., the number of parameters.
557 \subsection{Operations on Quasi-polynomials
}
560 In this section we discuss some of the more important
561 operations on
\ai[\tt]{evalue
}s provided by the
563 Some of these operations are extensions
564 of the functions from
\PolyLib/ with the same name.
566 Most of these operation are also provided by
\isl/ on
567 \ai[\tt]{isl
\_pw\_qpolynomial}s, which are set to replace
568 \ai[\tt]{evalue
}s. Use
\ai[\tt]{isl
\_pw\_qpolynomial\_from\_evalue} to convert
569 from
\ai[\tt]{evalue
}s to
\ai[\tt]{isl
\_pw\_qpolynomial}s.
571 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_evalue(
572 __isl_take isl_dim *dim, const evalue *e);
576 void eadd(const evalue *e1,evalue *res);
577 void emul(const evalue *e1, evalue *res);
579 The functions
\ai[\tt]{eadd
} and
\ai[\tt]{emul
} takes
580 two (pointers to)
\ai[\tt]{evalue
}s
\verb+e1+ and
\verb+res+
581 and computes their sum and product respectively.
582 The result is stored in
\verb+res+, overwriting (and deallocating)
583 the original value of
\verb+res+.
584 It is an error if exactly one of
585 the arguments of
\ai[\tt]{eadd
} is of type
\ai[\tt]{partition
}
586 (unless the other argument is
\verb+
0+).
587 The addition and multiplication operations are described
588 in
\citeN[Section~
4.5.1]{Verdoolaege2005PhD
}
589 and~
\citeN[Section~
4.5.2]{Verdoolaege2005PhD
}
592 The function
\ai[\tt]{eadd
} is an extension of the function
593 \ai[\tt]{new
\_eadd} from
\shortciteN{Seghir2002
}.
594 Apart from supporting the additional types from Section~
\ref{a:data
},
595 the new version also additionally imposes an order on the nesting of
596 different
\ai[\tt]{enode
}s.
597 Without such an ordering,
\ai[\tt]{evalue
}s could be constructed
598 representing for example
600 (
0 y^
0 + (
0 x^
0 +
1 x^
1 ) y^
1 ) x^
0 + (
0 y^
0 -
1 y^
1) x^
1
603 which is just a funny way of saying $
0$.
606 void eor(evalue *e1, evalue *res);
608 The function
\ai[\tt]{eor
} implements the
\ai{union
}
609 operation from
\citeN[Section~
4.5.3]{Verdoolaege2005PhD
}. Both arguments
610 are assumed to correspond to indicator functions.
613 evalue *esum(evalue *E, int nvar);
614 evalue *evalue_sum(evalue *E, int nvar, unsigned MaxRays);
616 The function
\ai[\tt]{esum
} has been superseded by
617 \ai[\tt]{evalue
\_sum}.
618 The function
\ai[\tt]{evalue
\_sum} performs the summation
619 operation from
\citeN[Section~
4.5.4]{Verdoolaege2005PhD
}.
620 The piecewise step-polynomial represented by
\verb+E+ is summated
621 over its first
\verb+nvar+ variables.
622 Note that
\verb+E+ must be zero or of type
\ai[\tt]{partition
}.
623 The function returns the result in a newly allocated
625 Note also that
\verb+E+ needs to have been converted
626 from
\ai[\tt]{fractional
}s to
\ai[\tt]{flooring
}s using
627 the function
\ai[\tt]{evalue
\_frac2floor}.
629 void evalue_frac2floor(evalue *e);
631 This function also ensures that the arguments of the
632 \ai[\tt]{flooring
}s are positive in the relevant chambers.
633 It currently assumes that the argument of each
634 \ai[\tt]{fractional
} in the original
\ai[\tt]{evalue
}
635 has a minimum in the corresponding chamber.
638 double compute_evalue(const evalue *e, Value *list_args);
639 Value *compute_poly(Enumeration *en,Value *list_args);
640 evalue *evalue_eval(const evalue *e, Value *values);
642 The functions
\ai[\tt]{compute
\_evalue},
643 \ai[\tt]{compute
\_poly} and
644 \ai[\tt]{evalue
\_eval}
645 evaluate a (piecewise) quasi-polynomial
646 at a certain point. The argument
\verb+list_args+
647 points to an array of
\ai[\tt]{Value
}s that is assumed
649 The
\verb+double+ return value of
\ai[\tt]{compute
\_evalue}
650 is inherited from
\PolyLib/.
653 void print_evalue(FILE *DST, const evalue *e, char **pname);
655 The function
\ai[\tt]{print
\_evalue} dumps a human-readable
656 representation to the stream pointed to by
\verb+DST+.
657 The argument
\verb+pname+ points
658 to an array of character strings representing the parameter names.
659 The array is assumed to be long enough.
662 int eequal(const evalue *e1, const evalue *e2);
664 The function
\ai[\tt]{eequal
} return true (
\verb+
1+) if its
665 two arguments are structurally identical.
666 I.e., it does
{\em not\/
} check whether the two
667 (piecewise) quasi-polynomial represent the same function.
670 void reduce_evalue (evalue *e);
672 The function
\ai[\tt]{reduce
\_evalue} performs some
673 simplifications on
\ai[\tt]{evalue
}s.
674 Here, we only describe the simplifications that are directly
675 related to the internal representation.
676 Some other simplifications are explained in
677 \citeN[Section~
4.7.2]{Verdoolaege2005PhD
}.
678 If the highest order coefficients of a
\ai[\tt]{polynomial
},
679 \ai[\tt]{fractional
} or
\ai[\tt]{flooring
} are zero (possibly
680 after some other simplifications), then the size of the array
681 is reduced. If only the constant term remains, i.e.,
682 the size is reduced to $
1$ for
\ai[\tt]{polynomial
} or to $
2$
683 for the other types, then the whole node is replaced by
685 Additionally, if the argument of a
\ai[\tt]{fractional
}
686 has been reduced to a constant, then the whole node
687 is replaced by its partial evaluation.
688 A
\ai[\tt]{relation
} is similarly reduced if its second
689 branch or both its branches are zero.
690 Chambers with zero associated quasi-polynomials are
691 discarded from a
\ai[\tt]{partition
}.
693 \subsection{Generating Functions
}
695 The representation of
\rgf/s uses
696 some basic types from the
\ai[\tt]{NTL
} library
\shortcite{NTL
}
697 for representing arbitrary precision integers
699 as well as vectors (
\ai[\tt]{vec
\_ZZ}) and matrices (
\ai[\tt]{mat
\_ZZ})
701 We further introduces a type
\ai[\tt]{QQ
} for representing a rational
702 number and use vectors (
\ai[\tt]{vec
\_QQ}) of such numbers.
709 NTL_vector_decl(QQ,vec_QQ);
712 Each term in a
\rgf/ is represented by a
\ai[\tt]{short
\_rat}
717 /* rows: terms in numerator */
722 /* rows: factors in denominator */
727 The fields
\ai[\tt]{n
} and
\ai[\tt]{d
} represent the
728 numerator and the denominator respectively.
729 Note that in our implementation we combine terms
730 with the same denominator.
731 In the numerator, each element of
\ai[\tt]{coeff
} and each row of
\ai[\tt]{power
}
732 represents a single such term.
733 The vector
\ai[\tt]{coeff
} contains the rational coefficients
734 $
\alpha_i$ of each term.
735 The columns of
\ai[\tt]{power
} correspond to the powers
737 In the denominator, each row of
\ai[\tt]{power
}
738 corresponds to the power $
\vec b_
{ij
}$ of a
739 factor in the denominator.
743 shows the internal representation of
745 \frac{\frac 3 2 \, x_0^
2 x_1^
3 +
2 \, x_0^
5 x_1^
{-
7}}
746 { (
1 - x_0 x_1^
{-
3}) (
1 - x_1^
2)
}
752 \begin{minipage
}{0cm
}
756 \begin{tabular
}{|c|c|c|
}
771 }+UC*++!D
\hbox{\tt short
\_rat}
775 \caption{Representation of
777 \left(
\frac 3 2 \, x_0^
2 x_1^
3 +
2 \, x_0^
5 x_1^
{-
7}\right)
778 /
\left( (
1 - x_0 x_1^
{-
3}) (
1 - x_1^
2)
\right)
785 The whole
\rgf/ is represented by a
\ai[\tt]{gen
\_fun}
788 typedef std::set<short_rat *,
789 short_rat_lex_smaller_denominator > short_rat_list;
795 void add(const QQ& c, const vec_ZZ& num, const mat_ZZ& den);
796 void add(short_rat *r);
797 void add(const QQ& c, const gen_fun *gf,
798 barvinok_options *options);
799 void substitute(Matrix *CP);
800 gen_fun *Hadamard_product(const gen_fun *gf,
801 barvinok_options *options);
802 void print(std::ostream& os,
803 unsigned int nparam, char **param_name) const;
804 operator evalue *() const;
805 ZZ coefficient(Value* params, barvinok_options *options) const;
806 void coefficient(Value* params, Value* c) const;
808 gen_fun(Polyhedron *C);
810 gen_fun(const gen_fun *gf);
814 A new
\ai[\tt]{gen
\_fun} can be constructed either as empty
\rgf/ (possibly
815 with a given context
\verb+C+), as a copy of an existing
\rgf/
\verb+gf+, or as
816 constant
\rgf/ with value for the constant term specified by
\verb+c+.
818 The first
\ai[\tt]{gen
\_fun::add
} method adds a new term to the
\rgf/,
819 described by the coefficient
\verb+c+, the numerator
\verb+num+ and the
820 denominator
\verb+den+.
821 It makes all powers in the denominator lexico-positive,
822 orders them in lexicographical order and inserts the new
823 term in
\ai[\tt]{term
} according to the lexicographical
824 order of the combined powers in the denominator.
825 The second
\ai[\tt]{gen
\_fun::add
} method adds
\verb+c+ times
\verb+gf+
828 The method
\ai[\tt]{gen
\_fun::operator evalue *
} performs
829 the conversion from
\rgf/ to
\psp/ explained in
830 \citeN[Section~
4.5.5]{Verdoolaege2005PhD
}.
831 The
\ai[\tt]{Polyhedron
} \ai[\tt]{context
} is the superset
832 of all points where the enumerator is non-zero used during this conversion,
833 i.e., it is the set $Q$ from
\citeN[Equation~
4.31]{Verdoolaege2005PhD
}.
834 If
\ai[\tt]{context
} is
\verb+NULL+ the maximal
835 allowed context is assumed, i.e., the maximal
836 region with lexico-positive rays.
838 The method
\ai[\tt]{gen
\_fun::coefficient
} computes the coefficient
839 of the term with power given by
\verb+params+ and stores the result
841 This method performs essentially the same computations as
842 \ai[\tt]{gen
\_fun::operator evalue *
}, except that it adds extra
843 equality constraints based on the specified values for the power.
845 The method
\ai[\tt]{gen
\_fun::substitute
} performs the
846 \ai{monomial substitution
} specified by the homogeneous matrix
\verb+CP+
847 that maps a set of ``
\ai{compressed parameter
}s''
\shortcite{Meister2004PhD
}
848 to the original set of parameters.
849 That is, if we are given a
\rgf/ $G(
\vec z)$ that encodes the
850 explicit function $g(
\vec i')$, where $
\vec i'$ are the coordinates of
851 the transformed space, and
\verb+CP+ represents the map
852 $
\vec i = A
\vec i' +
\vec a$ back to the original space with coordinates $
\vec i$,
853 then this method transforms the
\rgf/ to $F(
\vec x)$ encoding the
854 same explicit function $f(
\vec i)$, i.e.,
855 $$f(
\vec i) = f(A
\vec i' +
\vec a) = g(
\vec i ').$$
856 This means that the coefficient of the term
857 $
\vec x^
{\vec i
} =
\vec x^
{A
\vec i' +
\vec a
}$ in $F(
\vec x)$ should be equal to the
858 coefficient of the term $
\vec z^
{\vec i'
}$ in $G(
\vec z)$.
862 \sum_i \epsilon_i \frac{\vec z^
{\vec v_i
}}{\prod_j (
1-
\vec z^
{\vec b_
{ij
}})
}
867 \sum_i \epsilon_i \frac{\vec x^
{A
\vec v_i +
\vec a
}}
868 {\prod_j (
1-
\vec x^
{A
\vec b_
{ij
}})
}
872 The method
\ai[\tt]{gen
\_fun::Hadamard
\_product} computes the
873 \ai{Hadamard product
} of the current
\rgf/ with the
\rgf/
\verb+gf+,
874 as explained in
\citeN[Section~
4.5.2]{Verdoolaege2005PhD
}.
876 \subsection{Counting Functions
}
877 \label{a:counting:functions
}
879 Our library provides essentially three different counting functions:
880 one for non-parametric polytopes, one for parametric polytopes
881 and one for parametric sets with existential variables.
882 The old versions of these functions have a ``
\ai[\tt]{MaxRays
}''
883 argument, while the new versions have a more general
884 \ai[\tt]{barvinok
\_options} argument.
885 For more information on
\ai[\tt]{barvinok
\_options}, see Section~
\ref{a:options
}.
888 void barvinok_count(Polyhedron *P, Value* result,
890 void barvinok_count_with_options(Polyhedron *P, Value* result,
891 struct barvinok_options *options);
893 The function
\ai[\tt]{barvinok
\_count} or
894 \ai[\tt]{barvinok
\_count\_with\_options} enumerates the non-parametric
895 polytope
\verb+P+ and returns the result in the
\ai[\tt]{Value
}
896 pointed to by
\verb+result+, which needs to have been allocated
898 If
\verb+P+ is a union, then only the first set in the union will
899 be taken into account.
900 For the meaning of the argument
\verb+NbMaxCons+, see
901 the discussion on
\ai[\tt]{MaxRays
} in Section~
\ref{a:options
}.
903 The function
\ai[\tt]{barvinok
\_enumerate} for enumerating
904 parametric polytopes was meant to be
905 a drop-in replacement of
\PolyLib/'s
\ai[\tt]{Polyhedron
\_Enumerate}
907 Unfortunately, the latter has been changed to
908 accept an extra argument in recent versions of
\PolyLib/ as shown below.
910 Enumeration* barvinok_enumerate(Polyhedron *P, Polyhedron* C,
912 extern Enumeration *Polyhedron_Enumerate(Polyhedron *P,
913 Polyhedron *C, unsigned MAXRAYS, char **pname);
915 The argument
\verb+MaxRays+ has the same meaning as the argument
916 \verb+NbMaxCons+ above.
917 The argument
\verb+P+ refers to the $(d+n)$-dimensional
918 polyhedron defining the parametric polytope.
919 The argument
\verb+C+ is an $n$-dimensional polyhedron containing
920 extra constraints on the parameter space.
921 Its primary use is to indicate how many of the dimensions
922 in
\verb+P+ refer to parameters as any constraint in
\verb+C+
923 could equally well have been added to
\verb+P+ itself.
924 Note that the dimensions referring to the parameters should
926 If either
\verb+P+ or
\verb+C+ is a union,
927 then only the first set in the union will be taken into account.
928 The result is a newly allocated
\ai[\tt]{Enumeration
}.
929 As an alternative we also provide a function
930 (
\ai[\tt]{barvinok
\_enumerate\_ev} or
931 \ai[\tt]{barvinok
\_enumerate\_with\_options}) that returns
934 evalue* barvinok_enumerate_ev(Polyhedron *P, Polyhedron* C,
936 evalue* barvinok_enumerate_with_options(Polyhedron *P,
937 Polyhedron* C, struct barvinok_options *options);
940 For enumerating parametric sets with existentially quantified variables,
941 we provide two functions:
942 \ai[\tt]{barvinok
\_enumerate\_e},
944 \ai[\tt]{barvinok
\_enumerate\_isl}.
946 evalue* barvinok_enumerate_e(Polyhedron *P,
947 unsigned exist, unsigned nparam, unsigned MaxRays);
948 evalue* barvinok_enumerate_e_with_options(Polyhedron *P,
949 unsigned exist, unsigned nparam,
950 struct barvinok_options *options);
951 evalue *barvinok_enumerate_isl(Polyhedron *P,
952 unsigned exist, unsigned nparam,
953 struct barvinok_options *options);
954 evalue *barvinok_enumerate_scarf(Polyhedron *P,
955 unsigned exist, unsigned nparam,
956 struct barvinok_options *options);
958 The first function tries the simplification rules from
959 \citeN[Section~
4.6.2]{Verdoolaege2005PhD
} before resorting to the method
960 based on
\indac{PIP
} from
\citeN[Section~
4.6.3]{Verdoolaege2005PhD
}.
961 The second function immediately applies the technique from
962 \citeN[Section~
4.6.3]{Verdoolaege2005PhD
}.
963 The argument
\verb+exist+ refers to the number of existential variables,
965 the argument
\verb+nparam+ refers to the number of parameters.
966 The order of the dimensions in
\verb+P+ is:
967 counted variables first, then existential variables and finally
969 The function
\ai[\tt]{barvinok
\_enumerate\_scarf} performs the same
970 computation as the function
\ai[\tt]{barvinok
\_enumerate\_scarf\_series}
971 below, but produces an explicit representation instead of a generating function.
974 gen_fun * barvinok_series(Polyhedron *P, Polyhedron* C,
976 gen_fun * barvinok_series_with_options(Polyhedron *P,
977 Polyhedron* C, barvinok_options *options);
978 gen_fun *barvinok_enumerate_e_series(Polyhedron *P,
979 unsigned exist, unsigned nparam,
980 barvinok_options *options);
981 gen_fun *barvinok_enumerate_scarf_series(Polyhedron *P,
982 unsigned exist, unsigned nparam,
983 barvinok_options *options);
986 \ai[\tt]{barvinok
\_series} or
987 \ai[\tt]{barvinok
\_series\_with\_options} enumerates parametric polytopes
988 in the form of a
\rgf/.
989 The polyhedron
\verb+P+ is assumed to have only
990 revlex-positive rays.
992 The function
\ai[\tt]{barvinok
\_enumerate\_e\_series} computes a
993 generating function for the number of point in the parametric set
994 defined by
\verb+P+ with
\verb+exist+ existentially quantified
995 variables using the
\ai{projection theorem
}, as explained
996 in
\autoref{s:projection
}.
997 The function
\ai[\tt]{barvinok
\_enumerate\_scarf\_series} computes a
998 generating function for the number of point in the parametric set
999 defined by
\verb+P+ with
\verb+exist+ existentially quantified
1000 variables, which is assumed to be
2.
1001 This function implements the technique of
1002 \shortciteN{Scarf2006Neighborhood
} using the
\ai{neighborhood complex
}
1003 description of
\shortciteN{Scarf1981indivisibilities:II
}.
1004 It is currently restricted to problems with
3 or
4 constraints involving
1005 the existentially quantified variables.
1007 \subsection{Auxiliary Functions
}
1009 In this section we briefly mention some auxiliary functions
1010 available in the
\barvinok/ library.
1013 void Polyhedron_Polarize(Polyhedron *P);
1015 The function
\ai[\tt]{Polyhedron
\_Polarize}
1016 polarizes its argument and is explained
1017 in
\citeN[Section~
4.4.2]{Verdoolaege2005PhD
}.
1020 int unimodular_complete(Matrix *M, int row);
1022 The function
\ai[\tt]{unimodular
\_complete} extends
1023 the first
\verb+row+ rows of
1024 \verb+M+ with an integral basis of the orthogonal complement
1025 as explained in Section~
\ref{s:completion
}.
1027 if the resulting matrix is unimodular
\index{unimodular matrix
}.
1030 int DomainIncludes(Polyhedron *D1, Polyhedron *D2);
1032 The function
\ai[\tt]{DomainIncludes
} extends
1033 the function
\ai[\tt]{PolyhedronIncludes
}
1034 provided by
\PolyLib/
1035 to unions of polyhedra.
1036 It checks whether every polyhedron in the union
{\tt D2
}
1037 is included in some polyhedron of
{\tt D1
}.
1040 Polyhedron *DomainConstraintSimplify(Polyhedron *P,
1043 The value returned by
1044 \ai[\tt]{DomainConstraintSimplify
} is a pointer to
1045 a newly allocated
\ai[\tt]{Polyhedron
} that contains the
1046 same integer points as its first argument but possibly
1047 has simpler constraints.
1048 Each constraint $ g
\sp a x
\ge c $
1049 is replaced by $
\sp a x
\ge \ceil{ \frac c g
} $,
1050 where $g$ is the
\ac{gcd
} of the coefficients in the original
1052 The
\ai[\tt]{Polyhedron
} pointed to by
\verb+P+ is destroyed.
1055 Polyhedron* Polyhedron_Project(Polyhedron *P, int dim);
1057 The function
\ai[\tt]{Polyhedron
\_Project} projects
1058 \verb+P+ onto its last
\verb+dim+ dimensions.
1061 Matrix *left_inverse(Matrix *M, Matrix **Eq);
1063 The
\ai[\tt]{left
\_inverse} function computes the left inverse
1064 of
\verb+M+ as explained in Section~
\ref{s:inverse
}.
1066 \sindex{reduced
}{basis
}
1067 \sindex{generalized
}{reduced basis
}
1069 Matrix *Polyhedron_Reduced_Basis(Polyhedron *P,
1070 struct barvinok_options *options);
1072 \ai[\tt]{Polyhedron
\_Reduced\_Basis} computes
1073 a
\ai{generalized reduced basis
} of
{\tt P
}, which
1074 is assumed to be a polytope, using the algorithm
1075 of~
\shortciteN{Cook1993implementation
}.
1076 See
\autoref{s:feasibility
} for more information.
1077 The basis vectors are stored in the rows of the matrix returned.
1080 Vector *Polyhedron_Sample(Polyhedron *P,
1081 struct barvinok_options *options);
1083 \ai[\tt]{Polyhedron
\_Sample} returns an
\ai{integer point
} of
{\tt P
}
1084 or
{\tt NULL
} if
{\tt P
} contains no integer points.
1085 The integer point is found using the algorithm
1086 of~
\shortciteN{Cook1993implementation
} and uses
1087 \ai[\tt]{Polyhedron
\_Reduced\_Basis} to compute the reduced bases.
1088 See
\autoref{s:feasibility
} for more information.