Sven Verdoolaege [Sun, 6 Dec 2009 10:54:41 +0000 (11:54 +0100)]
isl_map_intersect: add special case for adding a single constraint
Sven Verdoolaege [Sat, 5 Dec 2009 17:50:12 +0000 (18:50 +0100)]
isl_map_is_subset: break off as soon as difference is known to be non-empty
Sven Verdoolaege [Mon, 7 Dec 2009 16:09:59 +0000 (17:09 +0100)]
compute set difference using a backtracking algorithm
In particular, treat all basic maps in the minuend separately
and only subtract parts of the subtrahend that actually overlap
with the minuend. Moreover, only use non-redundant constraints
when performing this subtraction.
Using only non-redundant constraints in overlapping parts
avoids the minuend being split in several parts unnecessarily.
Treating each basic map separately should help speed up
isl_map_is_subset in a subsequent commit.
Sven Verdoolaege [Tue, 1 Dec 2009 11:42:46 +0000 (12:42 +0100)]
isl_map_subtract.c: extract from isl_map.c
Sven Verdoolaege [Mon, 7 Dec 2009 16:00:15 +0000 (17:00 +0100)]
isl_tab: keep track of isl_basic_map instead of isl_basic_set
Sven Verdoolaege [Sat, 28 Nov 2009 20:47:29 +0000 (21:47 +0100)]
privately export isl_basic_map_contains
Sven Verdoolaege [Sat, 28 Nov 2009 20:44:28 +0000 (21:44 +0100)]
add isl_basic_map_add_ineq and isl_basic_map_add_eq
Sven Verdoolaege [Sat, 28 Nov 2009 19:16:03 +0000 (20:16 +0100)]
isl_tab_detect_redundant: return status instead of isl_tab *
Sven Verdoolaege [Sat, 28 Nov 2009 18:47:58 +0000 (19:47 +0100)]
isl_tab: add isl_tab_freeze_constraint
Sven Verdoolaege [Sat, 28 Nov 2009 15:09:56 +0000 (16:09 +0100)]
isl_tab_add_ineq and isl_tab_mark_empty: return status instead of isl_tab *
isl_tabs are not reference counted, so it's easier to deal with a status
than to have to keep track of whether the isl_tab may have been destroyed.
Sven Verdoolaege [Sun, 29 Nov 2009 18:34:13 +0000 (19:34 +0100)]
add missing AUTHORS file
Sven Verdoolaege [Sun, 29 Nov 2009 17:24:39 +0000 (18:24 +0100)]
isl_basic_set_swap_vars: re-gauss resulting bset
Many functions assume that their inputs have been gaussed.
Sven Verdoolaege [Mon, 16 Nov 2009 14:58:31 +0000 (15:58 +0100)]
add isl_basic_map_first_constraint
Sven Verdoolaege [Sun, 15 Nov 2009 19:28:40 +0000 (20:28 +0100)]
export isl_basic_map_lexmax
Sven Verdoolaege [Sun, 15 Nov 2009 17:22:07 +0000 (18:22 +0100)]
add isl_basic_set_lexmax
Sven Verdoolaege [Sun, 15 Nov 2009 16:31:52 +0000 (17:31 +0100)]
isl_map_drop_basic_map: consistently keep basic map argument
Sven Verdoolaege [Sun, 1 Nov 2009 14:41:28 +0000 (15:41 +0100)]
isl_tab: row is only (obviously) redundant if it does not depend on variables
Variables are not assumed to be nonnegative, but are only marked as being
nonnegative based on the constraints. This nonnegativity can therefore
not be used to mark rows as being redundant as that could lead to
circular reasoning.
Sven Verdoolaege [Sun, 1 Nov 2009 14:34:03 +0000 (15:34 +0100)]
isl_basic_map_simplify: make sure to rerun Gauss when equality has been added
remove_duplicate_constraints failed to set the progress flag when
it replaces a pair of inequalities by an equality, resulting in
the result of isl_basic_map_simplify possibly not having the equalities
in the expected form.
Sven Verdoolaege [Sun, 1 Nov 2009 13:49:46 +0000 (14:49 +0100)]
isl_tab_basic_map_partial_lexopt: use context constraints when detecting equalities
The constraints of the context of the actual map may conspire to form
equalities and we generally want to detect as many equalities as possible.
Therefore, detect equalities in the intersection of the two
and add these equalities to the map.
Note that the equalities are now no longer detected in the map
itself, so we may have to detect equalities again later if
we are ever interested in the equalities of the map itself.
Sven Verdoolaege [Sun, 1 Nov 2009 13:36:32 +0000 (14:36 +0100)]
isl_tab_pip.c: ignore dead columns when checking integrality
The dead columns are zero, which means that it does not matter
that they may have a fractional coefficient.
Moreover, dead columns can't be used to pivot, so it is actually
wrong to take them into account.
Sven Verdoolaege [Wed, 21 Oct 2009 21:49:13 +0000 (23:49 +0200)]
isl_pip: optionally perform some check on the results
Sven Verdoolaege [Wed, 21 Oct 2009 21:39:23 +0000 (23:39 +0200)]
put options in a separate isl_options structure
Sven Verdoolaege [Wed, 21 Oct 2009 21:22:39 +0000 (23:22 +0200)]
add rudimentary argument parsing facility
Sven Verdoolaege [Wed, 21 Oct 2009 19:04:26 +0000 (21:04 +0200)]
isl_tab_compute_reduced_basis: handle empty tables
Sven Verdoolaege [Wed, 21 Oct 2009 12:41:31 +0000 (14:41 +0200)]
isl_basic_set_solve_ilp: handle obviously empty sets
Sven Verdoolaege [Wed, 21 Oct 2009 12:31:22 +0000 (14:31 +0200)]
isl_basic_set_solve_ilp: fix handling of sets with equalities
First, the input set should be protected from being modified,
and second, the test for whether a solution is requested was wrong.
Sven Verdoolaege [Wed, 21 Oct 2009 12:05:13 +0000 (14:05 +0200)]
add isl_set_remove
Sven Verdoolaege [Wed, 21 Oct 2009 12:04:29 +0000 (14:04 +0200)]
add isl_set_fix
Sven Verdoolaege [Wed, 21 Oct 2009 12:01:53 +0000 (14:01 +0200)]
add isl_basic_set_fix
Sven Verdoolaege [Tue, 20 Oct 2009 10:34:24 +0000 (12:34 +0200)]
extract isl_basic_set_scan from polytope_scan.c
Sven Verdoolaege [Wed, 21 Oct 2009 16:13:19 +0000 (18:13 +0200)]
isl_basic_map_simplify: avoid removal of div definitions in eliminate_divs_eq
Sven Verdoolaege [Sun, 18 Oct 2009 16:24:26 +0000 (18:24 +0200)]
isl_map.c: declare variable at start of code block
Sven Verdoolaege [Sun, 18 Oct 2009 16:00:05 +0000 (18:00 +0200)]
isl_basic_set_project_out: handle rational sets
For rational sets, projection boils down to (Fourier-Motzkin)
elimination, so just call isl_basic_set_remove.
Sven Verdoolaege [Sun, 18 Oct 2009 15:52:51 +0000 (17:52 +0200)]
add isl_basic_set_remove
Sven Verdoolaege [Fri, 16 Oct 2009 12:46:28 +0000 (14:46 +0200)]
isl_tab_pip: keep cache of partial solutions
This cache allows us to combine two partial solutions into a single
partial solution if they have the same mapping. The domain of the
single partial solution is that before it was split to arrive at
the two domains of the two partial solutions.
In particular, this happens if it turns out there is no solution
in either part of the context.
It also happens when the initial set has existentially quantified
variables. In this case, we only insist that these variables
have an integer value, but we don't care about the actual value.
The solutions in the two parts of the context may therefore still
agree on the remaining variables.
Sven Verdoolaege [Fri, 16 Oct 2009 12:40:34 +0000 (14:40 +0200)]
isl_tab_pip: don't free isl_sol on error condition
Instead, set a flag. isl_sol is not reference counted, so it's better
not to destroy it along the way.
Sven Verdoolaege [Fri, 16 Oct 2009 12:30:24 +0000 (14:30 +0200)]
isl_tab: support generic undo records
Sven Verdoolaege [Fri, 16 Oct 2009 12:24:49 +0000 (14:24 +0200)]
add isl_mat_is_equal
Sven Verdoolaege [Fri, 16 Oct 2009 12:10:59 +0000 (14:10 +0200)]
isl_tab_pip.c: remove some code duplication between isl_map_add and isl_for_add
Sven Verdoolaege [Mon, 12 Oct 2009 12:12:55 +0000 (14:12 +0200)]
isl_map_is_subset: add special case for singleton maps
Sven Verdoolaege [Mon, 12 Oct 2009 08:26:07 +0000 (10:26 +0200)]
isl_map_compute_divs: skip computation if divs are known already
Sven Verdoolaege [Sat, 10 Oct 2009 13:09:10 +0000 (15:09 +0200)]
isl_map_is_subset: exploit another easy special case
Sven Verdoolaege [Sat, 10 Oct 2009 13:07:02 +0000 (15:07 +0200)]
add isl_map_fast_is_universe
Sven Verdoolaege [Sat, 10 Oct 2009 12:13:25 +0000 (14:13 +0200)]
add isl_set_size
Sven Verdoolaege [Sat, 10 Oct 2009 11:19:09 +0000 (13:19 +0200)]
mark some functions as requiring use of return value
Sven Verdoolaege [Sat, 10 Oct 2009 11:14:19 +0000 (13:14 +0200)]
isl_tab: improved error handling
Sven Verdoolaege [Thu, 8 Oct 2009 07:29:33 +0000 (09:29 +0200)]
isl_tab_pip.c: incrementally build recession cone of gbr context
When checking the feasibility of a constraint in the gbr context,
we compute a sample. The first step of this computation builds
a recession cone since we need to know which directions are unbounded.
By incrementally building up the recession cone, we can avoid
the complete recomputation. This is especially useful when
the context is/becomes bounded, since we can then avoid the
recession cone computation altogether.
Sven Verdoolaege [Mon, 12 Oct 2009 20:25:22 +0000 (22:25 +0200)]
isl_tab_pip.c: propagate some equalities from gbr context to main tableau
If a new equality in the context can be used to eliminate
a parameter in the main tableau, we perform the elimination
as this allows us to more easily determine the signs of rows
and it may avoid the introduction of some redundant integer
divisions.
Sven Verdoolaege [Mon, 5 Oct 2009 10:22:56 +0000 (12:22 +0200)]
isl_tab_pip.c: detect equalities in gbr context on each parametric cut
A new div that was introduced to express a parametric cut may,
within the current context, be an affine combination of other divs.
If so, we want to find these equalities as soon as possible
as this may allow us to more easily determine feasibility of
a constraint.
Sven Verdoolaege [Thu, 8 Oct 2009 12:14:10 +0000 (14:14 +0200)]
add isl_tab_detect_equalities
Sven Verdoolaege [Sun, 4 Oct 2009 14:38:28 +0000 (16:38 +0200)]
add isl_tab_set_initial_basis_with_cone
Sven Verdoolaege [Fri, 18 Sep 2009 07:02:40 +0000 (09:02 +0200)]
isl_tab_pip: use generalized basis reduction based context by default
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