doc/isl.tex

   1 \section{\protect\isl/ interface}
   2
   3 \subsection{Library}
   4
   5 The \barvinok/ library currently supports just two
   6 functions that interface with the \isl/ library.
   7 In time, this interface will grow and is set to replace
   8 the \PolyLib/ interface.
   9 For more information on the \isl/ data structures, see
  10 the \isl/ user manual.
  11
  12 \begin{verbatim}
  13 __isl_give isl_pw_qpolynomial *isl_set_card(__isl_take isl_set *set);
  14 \end{verbatim}
  15 Compute the number of elements in an \ai[\tt]{isl\_set}.
  16 The resulting \ai[\tt]{isl\_pw\_qpolynomial} has purely parametric cells.
  17
  18 \begin{verbatim}
  19 __isl_give isl_pw_qpolynomial *isl_map_card(__isl_take isl_map *map);
  20 \end{verbatim}
  21 Compute a closed form expression for the number of image elements
  22 associated to any element in the domain of the given \ai[\tt]{isl\_map}.
  23 The union of the cells in the resulting \ai[\tt]{isl\_pw\_qpolynomial}
  24 is equal to the domain of the input \ai[\tt]{isl\_map}.
  25
  26 \begin{verbatim}
  27 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sum(
  28         __isl_take isl_pw_qpolynomial *pwqp);
  29 \end{verbatim}
  30 Compute the sum of the given piecewise quasipolynomial over
  31 all integer points in the domain.  The result is a piecewise
  32 quasipolynomial that only involves the parameters.
  33
  34 \subsection{Calculator}
  35
  36 The \ai[\tt]{iscc} calculator offers an interface to some
  37 of the functionality provided by the \isl/ and \barvinok/
  38 libraries.
  39 The supported operations are shown in \autoref{t:iscc}.
  40 Here are some examples:
  41 \begin{verbatim}
  42 P := [n, m] -> { [i,j] : 0 <= i <= n and i <= j <= m };
  43 card P;
  44
  45 f := [n,m] -> { [i,j] -> i*j + n*i*i*j : i,j >= 0 and 5i + 27j <= n+m };
  46 sum f;
  47 s := sum f;
  48 s @ [n,m] -> { [] : 0 <= n,m <= 20 };
  49
  50 f := [n] -> { [i] -> 2*n*i - n*n + 3*n - 1/2*i*i - 3/2*i-1 :
  51                 (exists j : 0 <= i < 4*n-1 and 0 <= j < n and
  52                             2*n-1 <= i+j <= 4*n-2 and i <= 2*n-1 ) };
  53 ub f;
  54 u := ub f;
  55 u @ [n] -> { [] : 0 <= n <= 10 };
  56
  57 m := [n] -> { [i,j] -> [i+1,j+1] : 1 <= i,j < n;
  58               [i,j] -> [i+1,j-1] : 1 <= i < n and 2 <= j <= n };
  59 m^+;
  60 (m^+)[0];
  61 \end{verbatim}
  62
  63 \begin{table}
  64 \begin{tabular}{llp{0.5\textwidth}}
  65 Syntax & Result type & Meaning
  66 \\
  67 \hline
  68 \ai[\tt]{card} {\it set } & pw quasipolynomial &
  69 number of elements in the set
  70 \\
  71 \ai[\tt]{card} {\it map } & pw quasipolynomial &
  72 number of elements in the image of a domain element
  73 \\
  74 \ai[\tt]{dom} {\it map } & set &
  75 domain of map
  76 \\
  77 \ai[\tt]{ran} {\it map } & set &
  78 range of map
  79 \\
  80 \ai[\tt]{lexmin} {\it set } & set &
  81 lexicographically minimal element of a set
  82 \\
  83 \ai[\tt]{lexmin} {\it map } & map &
  84 lexicographically minimal image element
  85 \\
  86 \ai[\tt]{lexmax} {\it set } & set &
  87 lexicographically maximal element of a set
  88 \\
  89 \ai[\tt]{lexmax} {\it map } & map &
  90 lexicographically maximal image element
  91 \\
  92 \ai[\tt]{sample} {\it set } & set &
  93 a sample element of the set
  94 \\
  95 \ai[\tt]{sample} {\it map } & map &
  96 a sample element of the map
  97 \\
  98 \ai[\tt]{sum} {\it pw\_qp } & pw qp &
  99 sum over all integer points in the domain
 100 \\
 101 \ai[\tt]{ub} {\it pwqp } & pw qp fold &
 102 upper bound on the quasipolynomial over
 103 all integer points in the domain.
 104 This operation is only available if
 105 \ai[\tt]{GiNaC} support was compiled in.
 106 \\
 107 {\it set} \ai{$+$} {\it set} & set & union
 108 \\
 109 {\it map} \ai{$+$} {\it map} & map & union
 110 \\
 111 {\it pwqp} \ai{$+$} {\it pwqp} & pwqp & sum
 112 \\
 113 {\it set} \ai{$-$} {\it set} & set & set difference
 114 \\
 115 {\it map} \ai{$-$} {\it map} & map & set difference
 116 \\
 117 {\it pwqp} \ai{$-$} {\it pwqp} & pwqp & difference
 118 \\
 119 {\it set} \ai{$*$} {\it set} & set & intersection
 120 \\
 121 {\it map} \ai{$*$} {\it map} & map & intersection
 122 \\
 123 {\it pwqp} \ai{$*$} {\it pwqp} & pwqp & product
 124 \\
 125 {\it pwqp} \ai{@} {\it set} & pwqp &
 126 evaluate the piecewise quasipolynomial in each element
 127 of the set and return a piecewise quasipolynomial
 128 mapping each of the individual elements to the resulting
 129 constant
 130 \\
 131 {\it pwqpfold} \ai{@} {\it set} & pwqp &
 132 evaluate the piecewise quasipolynomial fold in each element
 133 of the set and return a piecewise quasipolynomial
 134 mapping each of the individual elements to the resulting
 135 constant
 136 \\
 137 {\it map} \ai[\tt]{\^{}+} & list &
 138 compute an overapproximation of the transitive closure
 139 and return a list containing the overapproximation
 140 and a boolean that is true if the overapproximation
 141 is known to be exact
 142 \\
 143 {\it list} [{\it int}] & &
 144 the element at the given position in the list
 145 \\
 146 \end{tabular}
 147 \caption{\protect\ai[\tt]{iscc} operations}
 148 \label{t:iscc}
 149 \end{table}