Lines Matching defs:and
1 \section{Sets and Relations}
17 and $\vec c \in \Z^m$.
44 and $\vec c \in \Z^m$.
75 Let $R \in \Z^n \to 2^{\Z^{d_1+d_2}}$ and
78 $R$ and $S$ is defined as
94 of differences between image elements and the corresponding
113 and even if it did, it would be fairly expensive to compute.
118 and an overapproximation of this hull is sufficient.
120 and it is defined as the (inclusion-wise) smallest basic set
124 and that the number of constraints in the simple hull is no
161 and in computing a unique representation for existentially quantified
164 \shortcite{BouletRe98,Verdoolaege2005experiences} and lies at the core
171 generating functions \cite{Woods2003short} and was inspired by the
176 method combined with Gomory cuts and describe some extensions
177 and optimizations. The main algorithm is applied to a matrix
179 there are two tableaus, one for the main problem and one for
197 between the variables $\vec x$ and non-negative variables
201 \end{pmatrix}$ and expresses the constraints $\vec y$ in the rows in terms
203 on a tableau exchanges a column and a row variable and is called a pivot.
208 zero and each row variable is assigned the constant term of the row.
215 greater than any solution, and gradually increments this sample value
231 that the zero vector is no greater than the minimal solution and
247 and will remain so because of the column choice explained above.
257 negative and/or positive values over the current set of possible
261 can only attain non-positive values and is not identically zero,
264 and negative values and split the context into a part where
265 it only attains non-negative values and a part where it only attains
282 with $\ceil\cdot$ the ceiling function and $\fract\cdot$ the
284 since $\vec c = \vec 0$ and $r = b(\vec p)$ is fractional, i.e.,
286 value of $r$ and $\vec c \ge 0$, the expression is non-negative
294 denominator of $\vec f$ and $g$. In practice, the variable
296 and the coefficients of the new constraint are adjusted accordingly.
303 \subsection{Negative Unknowns and Maximization}
307 sample value $\vec x = \vec 0$ and $\vec c$ is assumed to be non-negative
322 value will be of the form $\vec M + \vec v$ and the optimal value
341 add a big parameter, perform the reformulation and interpret the result
344 be computed and then these transformations are performed internally.
348 negative unknowns and maximization are by far the most common applications
349 of the big parameter and we believe that the user should not be bothered
353 can specify whether a maximum needs to be computed and no assumptions
355 is checked internally and a big parameter is automatically introduced when
371 \subsubsection{Feasibility Check and Detection of Equalities}
378 over the combined space of unknowns and parameters.
389 If the coefficients of the unknown and parameters in a constraint
393 {\tt isl} performs such simplifications on all sets and relations.
455 of the context and this context may have to be split for each
458 Instead, {\tt isl} introduces a new parameter, say $u$, and
466 on $u$ and therefore extends a solution to the new system.
473 and exploitation of symmetries that appear during the course of
484 will only have solutions for even values of $n$ and $n$ can be replaced
485 by $2n'$. Similarly, the parameters $n$ and $m$ in a system with
487 with $n=3n'$ and $m=2n'$.
507 sets and relations in {\tt isl}. Instead, {\tt isl} represents
518 representations and on allowing the output of {\tt isl\_pip} to optionally
527 but only in the constraints, and if moreover, the expression
534 and
547 the expression to be non-negative and one where the expression is
553 one that performs the recursive call and one, used by default, that
556 implementations and then discuss additional details of each of them.
566 evaluates to a positive number on some of these points and to a negative
569 possibility of a negative value and similarly in case of all
593 of each row and then selects the row where this largest coefficient is smaller
599 positive side, we will have fewer negative and indeterminate signs,
612 the dual simplex method incrementally on the context and backtrack
619 is always an integer point and that this point may also satisfy
622 we would not perform a feasibility test in such cases and then
652 and if (rationally) non-empty, any rational point
689 that we would only be measuring overhead such as input/output and conversions
690 and not the running time of the actual algorithm.
695 and {\tt PPL} version 0.11.2.
701 lexmax { [j1,j2] -> [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10] : 1 <= i1,j1 <= 8 and 1 <= i2,i3,i4,i5,i6,i7,i8,i9,i10 <= 2 and 1 <= j2 <= 128 and i1-1 = j1-1 and i2-1+2*i3-2+4*i4-4+8*i5-8+16*i6-16+32*i7-32+64*i8-64+128*i9-128+256*i10-256=3*j2-3+66 };
707 The remaining two come from \shortciteN{Verdoolaege2005experiences} and
710 The third and final group of test cases are borrowed from
711 \shortciteN{Bygde2010licentiate} and inspired the offline symmetry detection
713 are 11s and 5.9s.
714 All running times of {\tt barvinok} and {\tt isl} include a conversion
716 cases can be solved in 0.07s and 0.21s.
717 The {\tt PipLib} implementation has some fixed limits and will
758 \shortciteN{Bygde2010licentiate} and an analysis of the results
773 $b_j(\vec p)$ and one of the remaining $b_i(\vec p)$.
785 and such that exactly one of the elements of $\vec a$ is a $1$,
789 context constraints $t \ge -b(\vec p)$ and $t \ge 0$ and replace
793 by $t \ge -b(\vec p)$ while and non-negative value remains non-negative
797 solutions and that it does not introduce any spurious solutions.
803 Since $r = b(\vec p) + c_j - f \ge 0$ and $f \ge 0$, we have
809 and both of these are non-negative.
814 expressions in the internal representation of sets and relations
827 Let $R \in \Z^n \to 2^{\Z^{d+d}}$ be a relation and
868 $R^+$ and we want to detect the cases where the approximation is
873 and first compute an approximation of $R^k$ for $k \ge 1$ and then project
909 to arrive at an image element and ignore the fact that some of these
914 a total of $k$ offsets and then intersect domain and range of this
932 and with $\Delta_i$ the basic sets that compose
937 matter in which order we add the offsets and so we are allowed
952 and then the approximation computed in \eqref{eq:transitive:approx}
958 To ease both the exposition and the implementation, we will for
1003 and handled as in \eqref{eq:transitive:singleton}.
1028 such that for each row $j$ and for all $\vec s$,
1068 $k \in \Z_{\ge 1}$ and for every $\vec f \in k \, \Delta_i(\vec s)$
1097 and therefore also $A_3 \vec f \ge \vec r(\vec s)$.
1098 Note that if there are no mixed constraints and if the
1108 \right] \vec x' \,\}$ and therefore $\Delta'_i(\vec s)$ is
1127 We then have $k \, \spv a x < \spv a x$ for $k > 1$ and so the constraint
1131 $\vec b$ and $c$ need to be such that $- \spv b s - c \ge 0$ is a valid
1139 and intersected with the first set. The result is the set of coefficients
1170 { rat: coefficients[[c_cst, c_n] -> [i2, i3]] : i3 <= c_n and
1181 { rat: coefficients[[c_cst, c_n] -> []] : c_n >= 0 and 2c_n >= -c_cst }
1183 Negating these coefficients and intersecting with \verb+CD+,
1192 { rat: [[c_cst, c_n] -> [i2, i3]] : i3 <= c_n and
1193 i3 <= c_cst + 2c_n + i2 and c_n <= 0 and 2c_n <= -c_cst }
1202 [n] -> { rat: [i0, i1] : i1 <= -i0 and i0 >= 1 and i1 <= 2 - n - i0 }
1213 [n] -> { [x, y] -> [o0, o1] : o1 <= x + y - o0 and
1214 o0 >= 1 + x and o1 <= 2 - n + x + y - o0 and n >= 2 }
1221 of the parameters and others. The first set can be treated
1222 as parameters and the second as variables. Constraints involving
1239 of the parameters and variables as
1243 \text{and}
1302 are of type \eqref{eq:transitive:non-parametric} and they can therefore
1316 and so, by treating the parameters in a special way, we obtain
1330 and we obtain the approximation
1335 If we consider both $\diff R$ and $\diff R'$, then we obtain
1403 are zero and whose final coordinate is positive.
1405 Note that if $R^+$ is acyclic and $T$ is not, then the approximation
1406 is clearly not exact and the approximation of the power $K$
1415 For example, if $R = R_1 \cup R_2$ and $R_1 \circ R_2 = \emptyset$,
1424 of $R_1$ and $R_2$ separately.
1429 in any path that moves through both $R_1$ and $R_2$ to
1430 first move through $R_1$ and then through $R_2$.
1435 the basic relations and an edge between two basic relations
1436 $R_i$ and $R_j$ if $R_i$ needs to follow $R_j$ in some paths.
1449 separately and then compose them as in \eqref{eq:transitive:decompose}.
1451 important and should correspond to a topological ordering of the
1459 then the entire result is marked inexact and the exactness check
1470 \eqref{eq:transitive:edge} during the decomposition and if the
1521 Clearly, $R_1 \circ R_2 \subseteq R_2 \circ R_1$ and so
1607 and
1611 R1 := [n] -> { [i,j] -> [i+3,j] : i <= 2 j - 4 and i <= n - 3 and
1612 j <= 2 i - 1 and j <= n };
1613 R2 := [n] -> { [i,j] -> [i,j+3] : i <= 2 j - 1 and i <= n and
1614 j <= 2 i - 4 and j <= n - 3 };
1615 R3 := [n] -> { [i,j] -> [i+1,j+1] : i <= 2 j - 1 and i <= n - 1 and
1616 j <= 2 i - 1 and j <= n - 1 };
1623 and
1625 and so $R_1$ and $R_2$ form a strongly connected component.
1626 By computing the power of $R_3$ and $R_1 \cup R_2$ separately
1627 and composing the results, the power of $R$ can be computed exactly
1634 \subsection{Partitioning the domains and ranges of $R$}
1650 However, it is also possible to detect disjoint domains and ranges
1651 and to apply Floyd-Warshall internally.
1683 Let $D_{2i}$ be the domains of $R_i$ and $D_{2i+1}$ the ranges of $R_i$.
1688 the parts of the partition and as edges the $R_i$ attached to
1697 apply \autoref{a:Floyd} and return the union of all resulting
1701 possibly stay there for a while, and then go from $r$ to $q$.
1706 and $R_{rq}$ computed in the previous iteration of the
1740 \protect\shortciteN{Beletska2009} and its transitive closure}
1756 of the rightward relation and vice versa, but that the domain
1759 The domains and ranges can therefore be partitioned into two parts,
1760 $P_0$ and $P_1$, shown as the white and black dots in \autoref{f:COCOA:1},
1779 $R_{01}$ and $R_{10}$ are therefore also unaffected, but
1783 changed in the second iteration and it does not have an effect
1784 on $R_{01}$ and $R_{10}$. However, $R_{00}$ is updated to
1793 In some cases it is possible and useful to compute the transitive closure
1800 then we can pick some $R_i$ and compute the transitive closure of $R$ as
1824 the value $0$ in \eqref{eq:transitive:Q} and by using
1830 and $\range R_i$. We therefore need to check that domain
1831 and range of the transitive closure are part of ${\cal C}(R_i,D)$,
1833 are equal to the domain and range of $R_i$.
1835 the given choice of $R_i$ and $D$.
1839 to include both $\domain R$ and $\range R$, i.e., such
1860 and, similarly,
1958 designed to compute and underapproximation of the transitive closure,
1975 where $p$ ranges over the dimensions and $\vec L$, $\vec U$ and
1978 to that element, and similarly for $\vec L$.
1980 lower and upper bounds on the difference set $\Delta \, R$.
1992 The domain and range of this transitive closure are then
2025 ${\cal C}(R_i,D) - R_i^+$ is not a union and for each $j \ne i$