Sven Verdoolaege [Thu, 8 Oct 2009 12:10:30 +0000 (14:10 +0200)]
isl_tab_pip: add generalized basis reduction based context handling
Sven Verdoolaege [Thu, 8 Oct 2009 11:49:57 +0000 (13:49 +0200)]
isl_tab_pip.c: extract out context handling
Sven Verdoolaege [Thu, 17 Sep 2009 13:40:46 +0000 (15:40 +0200)]
isl_tab_pip.c: add_div: use more reliable way to test whether div is nonneg
Before, we used the fact that if all parameters are non-negative,
then the big parameter is not used.
However, it is perfectly valid to have negative parameters and
still not use any big parameter.
Sven Verdoolaege [Fri, 25 Sep 2009 17:17:20 +0000 (19:17 +0200)]
isl_tab_basic_map_partial_lexopt: remove samples that are no longer useful
When we test an inequality in row_sign, it is useful to store any
samples found, so we can use them to speed up the computation
of future row signs.
However, when we return from a branch, then all the samples found
since we entered the branch all satisfy the constraints on that
branch and so they will not satisfy the constraints on any other
branch. We therefore save the current number of samples when
we enter a branch and then discard all subsequently added samples
when we return from the branch.
Sven Verdoolaege [Mon, 5 Oct 2009 09:41:37 +0000 (11:41 +0200)]
isl_tab.c: extract out samples handling from isl_tab_pip.c
Sven Verdoolaege [Fri, 9 Oct 2009 15:16:24 +0000 (17:16 +0200)]
isl_affine_hull.c: uset_affine_hull_bounded: use tableaus to perform computation
Sven Verdoolaege [Tue, 29 Sep 2009 10:25:57 +0000 (12:25 +0200)]
isl_basic_map_detect_equalities: keep track of sample
Sven Verdoolaege [Tue, 29 Sep 2009 07:22:13 +0000 (09:22 +0200)]
isl_basic_map_detect_equalities: only compute recession cone once
Before, the recession cone was computed both during the computation
of the initial sample and then later again to project out this
recession cone.
Sven Verdoolaege [Sun, 4 Oct 2009 07:46:23 +0000 (09:46 +0200)]
isl_tab_sample: handle unbounded directions in initial basis
Sven Verdoolaege [Sun, 4 Oct 2009 07:33:06 +0000 (09:33 +0200)]
isl_tab_compute_reduced_basis: handle unbounded directions in initial basis
Sven Verdoolaege [Mon, 28 Sep 2009 19:20:19 +0000 (21:20 +0200)]
exploit equalities in isl_tab_sample
Sven Verdoolaege [Tue, 29 Sep 2009 08:25:40 +0000 (10:25 +0200)]
isl_tab: keep (in)equalities of bset (if any) in sync
Sven Verdoolaege [Tue, 6 Oct 2009 08:58:17 +0000 (10:58 +0200)]
isl_tab_sample: be more verbose about unbounded directions
Sven Verdoolaege [Sun, 27 Sep 2009 20:00:02 +0000 (22:00 +0200)]
separate out isl_tab_sample from sample_bounded
Sven Verdoolaege [Sat, 26 Sep 2009 14:42:31 +0000 (16:42 +0200)]
sample_bounded: reimplement to work directly on a tableau
In other words, adapt the implementation of isl_basic_set_samples
in polytope_scan.c
This avoids the reconstruction of tableaus and allows for a refactoring
that takes a tableau as input.
Sven Verdoolaege [Sat, 26 Sep 2009 13:49:55 +0000 (15:49 +0200)]
isl_tab_compute_reduced_basis: work with affine basis instead of linear basis
Sven Verdoolaege [Sat, 26 Sep 2009 13:31:12 +0000 (15:31 +0200)]
isl_tab_compute_reduced_basis: allow incremental computation
Sven Verdoolaege [Sat, 26 Sep 2009 13:05:07 +0000 (15:05 +0200)]
isl_polytope_scan: use isl_tab_from_basic_set
Sven Verdoolaege [Sat, 26 Sep 2009 11:20:40 +0000 (13:20 +0200)]
separate out isl_tab_reduced_basis from isl_basic_set_reduced_basis
This allows us to compute a reduced basis on a set given in tableau form.
Sven Verdoolaege [Fri, 25 Sep 2009 10:57:10 +0000 (12:57 +0200)]
basis_reduction_tab.c: use isl_tab_product to construct product tableau
Before, we would manually construct a tableau for the Cartesian
product of a set with itself. Now, we first create a tableau
for the set and then construct the product tableau.
This should be more efficient and allows us to refactor
the code to pass in a tableau instead of a set.
Sven Verdoolaege [Thu, 8 Oct 2009 20:53:30 +0000 (22:53 +0200)]
add isl_tab_product
Sven Verdoolaege [Wed, 7 Oct 2009 18:28:30 +0000 (20:28 +0200)]
isl_basic_set_reduced_basis: fix value in directions with only one integer value
If two or more directions have a width that is smaller than one,
i.e., such that the only one integer value can be attained,
then the standard algorithm would still try to order these
directions. However, if the first directions only admit one
value, then it doesn't matter in which order they are put.
We therefore keep track of such directions explicitly and
also set the value in the tableau to the fixed value, rather
than keeping the rational interval with only one integer value.
Sven Verdoolaege [Fri, 9 Oct 2009 08:40:23 +0000 (10:40 +0200)]
isl_basic_set_reduced_basis: fix up documentation
Sven Verdoolaege [Fri, 25 Sep 2009 10:46:06 +0000 (12:46 +0200)]
basis_reduction_tab.c: keep track of con_offset instead of n_ineq
This is a minor cosmetic change.
Sven Verdoolaege [Thu, 8 Oct 2009 12:43:07 +0000 (14:43 +0200)]
add isl_tab_add_eq
Sven Verdoolaege [Wed, 7 Oct 2009 18:19:03 +0000 (20:19 +0200)]
isl_tab_add_valid_eq: add special treatment for manifestly zero rows
Sven Verdoolaege [Thu, 17 Sep 2009 10:09:46 +0000 (12:09 +0200)]
isl_tab_extend_cons: check tab argument
Sven Verdoolaege [Tue, 29 Sep 2009 12:13:29 +0000 (14:13 +0200)]
rename isl_tab_detect_equalities to isl_tab_detect_implicit_equalities
Sven Verdoolaege [Sun, 27 Sep 2009 19:38:20 +0000 (21:38 +0200)]
isl_tab_from_recession_cone: take basic set instead of basic map as argument
Sven Verdoolaege [Sun, 27 Sep 2009 16:55:27 +0000 (18:55 +0200)]
isl_ilp.c: separate out solve_ilp_search
Sven Verdoolaege [Sat, 26 Sep 2009 15:54:58 +0000 (17:54 +0200)]
isl_sample.c: basic_set_sample: remember boundedness of basic set
Sven Verdoolaege [Mon, 28 Sep 2009 13:41:01 +0000 (15:41 +0200)]
add isl_polyhedron_detect_equalities test application
Sven Verdoolaege [Mon, 28 Sep 2009 13:40:24 +0000 (15:40 +0200)]
add isl_basic_set_detect_equalities
Sven Verdoolaege [Mon, 28 Sep 2009 13:00:39 +0000 (15:00 +0200)]
isl_tab_allocate_con: add extra assertion
Sven Verdoolaege [Sat, 26 Sep 2009 13:40:13 +0000 (15:40 +0200)]
isl_sample.c: basic_set_reduced: fix typo preventing use of gbr_only_first
Sven Verdoolaege [Sun, 4 Oct 2009 08:20:51 +0000 (10:20 +0200)]
isl_tab_basic_map_partial_lexopt: simplify result
Sven Verdoolaege [Tue, 29 Sep 2009 08:11:33 +0000 (10:11 +0200)]
privately export isl_basic_set_add_{in,}eq
Sven Verdoolaege [Wed, 7 Oct 2009 15:06:42 +0000 (17:06 +0200)]
privately export isl_basic_set_sample_with_cone
Sven Verdoolaege [Wed, 7 Oct 2009 15:02:02 +0000 (17:02 +0200)]
add isl_basic_set_underlying_set
Sven Verdoolaege [Wed, 7 Oct 2009 10:19:41 +0000 (12:19 +0200)]
isl_tab.c: close_row: push undo record for setting row to zero
Sven Verdoolaege [Sun, 4 Oct 2009 07:12:45 +0000 (09:12 +0200)]
add isl_mat_vec_inverse_product
Sven Verdoolaege [Fri, 2 Oct 2009 12:34:39 +0000 (14:34 +0200)]
add isl_mat_concat
Sven Verdoolaege [Mon, 28 Sep 2009 10:41:53 +0000 (12:41 +0200)]
add isl_int_divexact_ui
Sven Verdoolaege [Mon, 5 Oct 2009 21:15:30 +0000 (23:15 +0200)]
add isl_set_dim_residue_class
Sven Verdoolaege [Sat, 3 Oct 2009 13:01:56 +0000 (15:01 +0200)]
fix long standing bug in isl_mat_inverse_product
Sven Verdoolaege [Thu, 1 Oct 2009 19:48:17 +0000 (21:48 +0200)]
add isl_basic_map_foreach_lexmin
Sven Verdoolaege [Thu, 1 Oct 2009 09:42:19 +0000 (11:42 +0200)]
add isl_set_project_out
Sven Verdoolaege [Thu, 1 Oct 2009 09:23:05 +0000 (11:23 +0200)]
add isl_set_detect_equalities
Sven Verdoolaege [Thu, 1 Oct 2009 09:18:13 +0000 (11:18 +0200)]
add isl_set_foreach_basic_set
Sven Verdoolaege [Wed, 30 Sep 2009 19:17:11 +0000 (21:17 +0200)]
add isl_set_lifting
Sven Verdoolaege [Wed, 30 Sep 2009 13:11:33 +0000 (15:11 +0200)]
isl_dim_size: check argument
Sven Verdoolaege [Wed, 30 Sep 2009 10:37:35 +0000 (12:37 +0200)]
export isl_mat header
Sven Verdoolaege [Wed, 30 Sep 2009 10:30:47 +0000 (12:30 +0200)]
add isl_basic_map_lexmin
Sven Verdoolaege [Wed, 30 Sep 2009 10:20:18 +0000 (12:20 +0200)]
add isl_map_foreach_basic_map
Sven Verdoolaege [Mon, 21 Sep 2009 15:55:02 +0000 (17:55 +0200)]
configure.ac: fix cut-and-paste error in original commit
Sven Verdoolaege [Mon, 21 Sep 2009 15:41:41 +0000 (17:41 +0200)]
add isl_int_get_si
Sven Verdoolaege [Mon, 21 Sep 2009 15:23:21 +0000 (17:23 +0200)]
export isl_set_sample
Sven Verdoolaege [Mon, 21 Sep 2009 15:06:45 +0000 (17:06 +0200)]
add isl_basic_set_universe_like_set
Sven Verdoolaege [Mon, 21 Sep 2009 07:55:07 +0000 (09:55 +0200)]
add isl_set_is_strict_subset
Sven Verdoolaege [Sun, 20 Sep 2009 22:54:27 +0000 (00:54 +0200)]
add isl_set_universe_like
Sven Verdoolaege [Sun, 20 Sep 2009 16:09:43 +0000 (18:09 +0200)]
AX_SUBMODULE: set PKG_CONFIG_PATH
Sven Verdoolaege [Sun, 20 Sep 2009 13:23:07 +0000 (15:23 +0200)]
create pkg-config file
Sven Verdoolaege [Sun, 20 Sep 2009 09:54:11 +0000 (11:54 +0200)]
AX_SUBMODULE: drop options that are meaningless given possible choices
Sven Verdoolaege [Wed, 16 Sep 2009 11:19:12 +0000 (13:19 +0200)]
isl_basic_map_from_constraint: return copy of bmap in constraint if possible
Commit fa1cd4b (isl_basic_map_add_constraint: handle constraints obtained from
basic maps) fixed isl_basic_map_add_constraint to also work with constraints
obtained from iterating over the constraints of a basic map by
calling isl_basic_map_from_constraint.
However, this broke the case where a new constraint is created with
existentially quantified variables. In this case, the divs may be
unknown and we can't compute them because that may result in a union.
So, try to detect this special case in isl_basic_map_from_constraint
and return the basic map stored inside the constraint.
Sven Verdoolaege [Wed, 16 Sep 2009 09:08:42 +0000 (11:08 +0200)]
doc: fix description of lexicograhpic order relations
Sven Verdoolaege [Wed, 16 Sep 2009 09:06:24 +0000 (11:06 +0200)]
add isl_map_lex_le and isl_map_lex_ge
Sven Verdoolaege [Mon, 14 Sep 2009 16:13:20 +0000 (18:13 +0200)]
export isl_basic_map_gist
Sven Verdoolaege [Mon, 14 Sep 2009 15:53:51 +0000 (17:53 +0200)]
add isl_basic_map_sample and isl_map_sample
Sven Verdoolaege [Sun, 13 Sep 2009 17:39:17 +0000 (19:39 +0200)]
isl_sample.c: move isl_basic_set_from_vec from isl_affine_hull.c
Sven Verdoolaege [Sun, 13 Sep 2009 17:26:19 +0000 (19:26 +0200)]
rename isl_basic_set_sample to isl_basic_set_sample_vec
Sven Verdoolaege [Sun, 13 Sep 2009 17:22:37 +0000 (19:22 +0200)]
make some internal functions static
Sven Verdoolaege [Sun, 13 Sep 2009 17:13:13 +0000 (19:13 +0200)]
isl_basic_map_add_constraint: handle constraints obtained from basic maps
The bmap field of a constraint may contain a basic map that is bounded
by more than one constraint. The constraint can therefore not be
added by simply taking the intersection with this bmap.
Instead, first create a basic map that exactly corresponds to the constraint
and then take the intersection with that basic map.
Sven Verdoolaege [Sun, 13 Sep 2009 16:39:02 +0000 (18:39 +0200)]
add isl_basic_map_from_constraint
Sven Verdoolaege [Sat, 12 Sep 2009 17:50:54 +0000 (19:50 +0200)]
isl_map_simplify.c: break if set turns out to be empty during div coalescing
Sven Verdoolaege [Sat, 12 Sep 2009 16:11:12 +0000 (18:11 +0200)]
add isl_basic_map_universe_like
Sven Verdoolaege [Tue, 8 Sep 2009 08:38:03 +0000 (09:38 +0100)]
add isl_map_lex_lt and isl_map_lex_gt
Sven Verdoolaege [Wed, 9 Sep 2009 18:32:35 +0000 (20:32 +0200)]
isl_tab.c: cut_to_hyperplane: do nothing if selected constraint is an equality
Sven Verdoolaege [Wed, 9 Sep 2009 12:54:16 +0000 (14:54 +0200)]
reverse meaning of isl_basic_map_{less,more}_at
Before, these functions were interpreted as returning maps that map elements
to elements that are less/more.
Now, they are interpreted as returning relations that express
the concept of being less/more, i.e., the elements in the domain
are now less/more than the elements in the range.
Sven Verdoolaege [Tue, 8 Sep 2009 14:34:24 +0000 (16:34 +0200)]
isl_tab_dup: avoid out-of-bounds array access
tab->n_col is between 0 and mat->n_col - 2 - M
and may not be equal to n_var after some columns have been dropped.
Sven Verdoolaege [Sun, 6 Sep 2009 15:49:15 +0000 (17:49 +0200)]
isl 0.01
Sven Verdoolaege [Sun, 6 Sep 2009 16:00:03 +0000 (18:00 +0200)]
add a rudimentary manual
Sven Verdoolaege [Sun, 6 Sep 2009 15:59:28 +0000 (17:59 +0200)]
add some memory management annotations
Sven Verdoolaege [Sun, 6 Sep 2009 13:33:53 +0000 (15:33 +0200)]
export isl_basic_set_project_out
Sven Verdoolaege [Sun, 6 Sep 2009 11:48:04 +0000 (13:48 +0200)]
isl_basic_set_normalize_constraints: add missing return
Sven Verdoolaege [Sun, 6 Sep 2009 11:46:47 +0000 (13:46 +0200)]
isl_map_simplify.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:44:45 +0000 (13:44 +0200)]
isl_map.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:43:09 +0000 (13:43 +0200)]
isl_basic_set_get_hash: initialize hash value
Sven Verdoolaege [Sun, 6 Sep 2009 11:40:52 +0000 (13:40 +0200)]
isl_affine_hull.c: remove unused variable
Sven Verdoolaege [Sun, 6 Sep 2009 11:40:24 +0000 (13:40 +0200)]
isl_hash.c: remove unused variable
Sven Verdoolaege [Sun, 6 Sep 2009 11:39:11 +0000 (13:39 +0200)]
isl_lp.c: add missing include
Sven Verdoolaege [Sun, 6 Sep 2009 11:38:02 +0000 (13:38 +0200)]
isl_equalities.c: drop redundant error handling
Sven Verdoolaege [Sun, 6 Sep 2009 11:37:44 +0000 (13:37 +0200)]
isl_equalities.c: remove unused variable
Sven Verdoolaege [Sun, 6 Sep 2009 11:36:21 +0000 (13:36 +0200)]
isl_convex_hull.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:34:20 +0000 (13:34 +0200)]
isl_constraint.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:30:12 +0000 (13:30 +0200)]
isl_tab.c: sign_of_min: only pivot back if we performed any pivot
Sven Verdoolaege [Sun, 6 Sep 2009 11:23:29 +0000 (13:23 +0200)]
isl_tab.c: isl_tab_mark_redundant: fix up error return
Sven Verdoolaege [Sun, 6 Sep 2009 11:22:11 +0000 (13:22 +0200)]
isl_tab.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:20:49 +0000 (13:20 +0200)]
isl_tab_pip.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:19:05 +0000 (13:19 +0200)]
isl_vec.c: remove unused variable
Sven Verdoolaege [Sun, 6 Sep 2009 11:18:31 +0000 (13:18 +0200)]
isl_test.c: remove unused variable