From 972d64f64336e0b2e84322821807484d2142ed71 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 21 Apr 2010 17:15:51 +0200 Subject: [PATCH] doc: document simple hull --- doc/implementation.tex | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ doc/user.pod | 18 ++++++++++++++++++ include/isl_map.h | 1 + include/isl_set.h | 2 +- 4 files changed, 69 insertions(+), 1 deletion(-) diff --git a/doc/implementation.tex b/doc/implementation.tex index 0257d063..663f46f1 100644 --- a/doc/implementation.tex +++ b/doc/implementation.tex @@ -102,6 +102,55 @@ $$ $$ \end{definition} +\section{Simple Hull}\label{s:simple hull} + +It is sometimes useful to have a single +basic set or basic relation that contains a given set or relation. +For rational sets, the obvious choice would be to compute the +(rational) convex hull. For integer sets, the obvious choice +would be the integer hull. +However, {\tt isl} currently does not support an integer hull operation +and even if it did, it would be fairly expensive to compute. +The convex hull operation is supported, but it is also fairly +expensive to compute given only an implicit representation. + +Usually, it is not required to compute the exact integer hull, +and an overapproximation of this hull is sufficient. +The ``simple hull'' of a set is such an overapproximation +and it is defined as the (inclusion-wise) smallest basic set +that is described by constraints that are translates of +the constraints in the input set. +This means that the simple hull is relatively cheap to compute +and that the number of constraints in the simple hull is no +larger than the number of constraints in the input. +\begin{definition}[Simple Hull of a Set] +The {\em simple hull} of a set +$S = \bigcup_{1 \le i \le v} S_i$, with +$$ +S : \Z^n \to 2^{\Z^d} : \vec s \mapsto +S(\vec s) = +\left\{\, \vec x \in \Z^d \mid \exists \vec z \in \Z^e : +\bigvee_{1 \le i \le v} +A_i \vec x + B_i \vec s + D_i \vec z + \vec c_i \geq \vec 0 \,\right\} +$$ +is the set +$$ +H : \Z^n \to 2^{\Z^d} : \vec s \mapsto +S(\vec s) = +\left\{\, \vec x \in \Z^d \mid \exists \vec z \in \Z^e : +\bigwedge_{1 \le i \le v} +A_i \vec x + B_i \vec s + D_i \vec z + \vec c_i + \vec K_i \geq \vec 0 +\,\right\} +, +$$ +with $\vec K_i$ the (component-wise) smallest non-negative integer vectors +such that $S \subseteq H$. +\end{definition} +The $\vec K_i$ can be obtained by solving a number of +LP problems, one for each element of each $\vec K_i$. +If any LP problem is unbounded, then the corresponding constraint +is dropped. + \section{Coalescing}\label{s:coalescing} See \shortciteN{Verdoolaege2009isl}, for now. diff --git a/doc/user.pod b/doc/user.pod index 0fab92bb..e2f496d4 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -893,6 +893,24 @@ basic set or relation. If the input set or relation has any existentially quantified variables, then the result of these operations is currently undefined. +=item * Simple hull + + __isl_give isl_basic_set *isl_set_simple_hull( + __isl_take isl_set *set); + __isl_give isl_basic_map *isl_map_simple_hull( + __isl_take isl_map *map); + +These functions compute a single basic set or relation +that contains the whole input set or relation. +In particular, the output is described by translates +of the constraints describing the basic sets or relations in the input. + +=begin latex + +(See \autoref{s:simple hull}.) + +=end latex + =item * Affine hull __isl_give isl_basic_set *isl_basic_set_affine_hull( diff --git a/include/isl_map.h b/include/isl_map.h index ac146ae9..69c2098a 100644 --- a/include/isl_map.h +++ b/include/isl_map.h @@ -149,6 +149,7 @@ __isl_give isl_basic_map *isl_basic_map_universe(__isl_take isl_dim *dim); __isl_give isl_basic_map *isl_basic_map_universe_like( __isl_keep isl_basic_map *bmap); struct isl_basic_map *isl_basic_map_convex_hull(struct isl_basic_map *bmap); +__isl_give isl_basic_map *isl_map_simple_hull(__isl_take isl_map *map); __isl_give isl_basic_map *isl_basic_map_intersect_domain( __isl_take isl_basic_map *bmap, diff --git a/include/isl_set.h b/include/isl_set.h index f6ebe4bc..d76bb522 100644 --- a/include/isl_set.h +++ b/include/isl_set.h @@ -211,7 +211,7 @@ __isl_give isl_point *isl_set_sample_point(__isl_take isl_set *set); __isl_give isl_set *isl_set_detect_equalities(__isl_take isl_set *set); __isl_give isl_basic_set *isl_set_affine_hull(__isl_take isl_set *set); __isl_give isl_basic_set *isl_set_convex_hull(__isl_take isl_set *set); -struct isl_basic_set *isl_set_simple_hull(struct isl_set *set); +__isl_give isl_basic_set *isl_set_simple_hull(__isl_take isl_set *set); struct isl_basic_set *isl_set_bounded_simple_hull(struct isl_set *set); __isl_give isl_set *isl_set_recession_cone(__isl_take isl_set *set); -- 2.11.4.GIT