isl/doc/implementation.tex

112 However, {\tt isl} currently does not support an integer hull operation
115 expensive to compute given only an implicit representation.
118 and an overapproximation of this hull is sufficient.
119 The ``simple hull'' of a set is such an overapproximation
213 The dual simplex method starts from an initial sample value that
276 with $b(\vec p)$ the constant term, an affine expression in the
311 an arbitrarily large positive number.  Instead of looking for the
336 $\fract {\alpha M } = 0$.  It should be noted, though, that an unbounded
338 indicates an incorrect formulation of the problem.
363 produce an error if the problem turns out to be unbounded.
404 Given an equality involving at least one unknown, we pivot
511 to disjunctive normal form can lead to an explosion of the size
521 Currently, {\tt isl} also does not have an internal representation
538 an increase by a factor of $n!$ if all possible orderings end up being
544 on the sign of an affine expression over the elements of the context.
580 When an extra integer division is added to the context,
588 but there are rows with an indeterminate sign, then the context
617 an extra constraint to the context.
619 is always an integer point and that this point may also satisfy
624 in an accumulation of a large number of cuts.
653 in the set can be rounded up to yield an integer point in the context.
673 The list of witnesses is used to construct an initial approximation
676 Any equality found in this way that expresses an integer division
677 as an \emph{integer} affine combination of other variables is
686 run on an Intel Xeon W3520 @ 2.66GHz.
758 \shortciteN{Bygde2010licentiate} and an analysis of the results
762 In this section, we present an online detection mechanism that has
861 we can, in the general case, only compute an approximation
871 For computing an approximation of the transitive closure of $R$,
873 and first compute an approximation of $R^k$ for $k \ge 1$ and then project
895 \subsection{Computing an Approximation of $R^k$}
909 to arrive at an image element and ignore the fact that some of these
961 That is, each offset is extended with an extra coordinate that is
1001 Let us now consider how to compute an overapproximation of $P_i'$.
1004 Note that this is just an optimization.  The procedure described
1066 To prove that $Q_i$ is indeed an overapproximation of $P_i'$,
1353 Since $K$ is an overapproximation of $R^k$, $T$ will also be an
1366 Since $T$ is known to be an overapproximation, we only need to check
1382 to be an overapproximation, we only need to check whether
1400 an overapproximation of $R^+$, also
1414 an approximation of each strongly connected components separately.
1435 the basic relations and an edge between two basic relations
1437 That is, there is an edge from $R_i$ to $R_j$ iff
1455 That is, whenever the algorithm checks if there is an edge between
1465 still be an overapproximation of the left hand side, but this result
1631 an overapproximation of the power.
1642 In particular, when an entire dependence graph is encoded
1708 However, from an implementation perspective, it is easier
1718 The result of the recursive call will either be exact or an
1720 also exact or an overapproximation.
1783 changed in the second iteration and it does not have an effect
1848 or at least an approximation of this convex hull.
1960 In this section, we describe our implementation of an algorithm
1979 Such an overapproximation can be obtained by computing strides,
2000 If an upper bound is required, it can be calculated in a manner