Sven Verdoolaege [Fri, 28 Aug 2009 17:40:58 +0000 (19:40 +0200)]
isl_basic_map_remove: only drop divs if basic map did not turn out to be empty
If isl_basic_map_eliminate_vars finds that its argument is empty,
it resets its constraints to the canonical representation of an empty
set and drops all divs.
Sven Verdoolaege [Thu, 13 Aug 2009 14:01:56 +0000 (16:01 +0200)]
isl_basic_map_detect_equalities: explicitly keep track of any equalities found
The way extend_affine_hull works is that it starts off from an
under-approximation of the affine hull and then extends it with
each extra point found outside of the current approximation.
The affine hull is then determined by the equalities that remain.
However, during the computation, we may find an equality in
the current approximation such that there is no point in the set
outside of this equality. If the approximation is later extended
with a point found outside some other equality, then this first
equality would get tested again. If this is a difficult computation,
then we needlessly go through it again.
By explicitly storing the equality that we have detected in the set,
this computation becomes trivial, to there is no real harm in doing
again. An alternative would be to keep track of all equalities found
in some additional data structure, but adding it to the original set
seems preferable since it may also simplify tests for points outside
other equalities.
Perhaps the calling convention should be changed such that
extend_affine_hull would return the original set intersected
with its affine hull, rather than the affine hull itself.
Sven Verdoolaege [Thu, 13 Aug 2009 14:01:12 +0000 (16:01 +0200)]
isl_basic_map_extend_dim: keep hold of sample if dimension doesn't change
Sven Verdoolaege [Sat, 8 Aug 2009 18:08:16 +0000 (20:08 +0200)]
isl_tab_min: read off all information from tableau before rollback
As it happens, the rollback has little effect in this case and
the information is still available, but we shouldn't depend on this.
Sven Verdoolaege [Sat, 8 Aug 2009 18:02:40 +0000 (20:02 +0200)]
isl_tab_add_valid_eq: keep track of whether equality is negated
This is important during generalized basis reduction, because
this procedure requires the dual variables of some of the
equalities added to the tableau. If the original equality get
negated then the dual of the original equality will be the
opposite of the dual of the equality that was actually added.
Without this fix, gbr could in some cases make completely
inappropriate decisions.
Sven Verdoolaege [Fri, 7 Aug 2009 12:29:56 +0000 (14:29 +0200)]
configure.ac: no longer use piplib by default
Sven Verdoolaege [Wed, 22 Jul 2009 12:48:07 +0000 (14:48 +0200)]
add an internal parametric integer linear program solver
This removes the dependence on piplib.
The solver is very similar to the one in piplib.
In particular, as in piplib, the lexicographic solver is
used recursively on the context. This means that the current
solver will run into the same problems the piplib solver runs into
while looking for an integer point in a context that no longer has any.
In the future, we will replace this recursive call by a call
to an incremental solver based on the generalized basis reduction solver.
Sven Verdoolaege [Thu, 6 Aug 2009 14:15:56 +0000 (16:15 +0200)]
isl_mat_extend: make sure the number of rows never decreases
Sven Verdoolaege [Thu, 6 Aug 2009 10:20:46 +0000 (12:20 +0200)]
isl_affine_hull.c: only construct affine hull in bounded directions
The affine hull of a set necessarily contains the directions
of the recession cone of the set.
Before we exploited this fact by adding these directions to
our initial approximation of the affine hull.
The set for which the affine hull was computed was not changed, however.
Now, we project out the recession cone and only construct an
affine hull in the remaining part.
Sven Verdoolaege [Fri, 7 Aug 2009 08:07:44 +0000 (10:07 +0200)]
isl_tab: add support for keeping track of samples
Sven Verdoolaege [Wed, 5 Aug 2009 09:01:05 +0000 (11:01 +0200)]
isl_tab: optionally keep track of row signs
Sven Verdoolaege [Wed, 5 Aug 2009 08:49:48 +0000 (10:49 +0200)]
isl_tab: add isl_basic_set field for optionally keeping track of inequalities
Sven Verdoolaege [Wed, 5 Aug 2009 08:22:52 +0000 (10:22 +0200)]
isl_tab: introduce support for "big parameters"
These will be used while solving PILP problems.
Sven Verdoolaege [Wed, 5 Aug 2009 08:02:02 +0000 (10:02 +0200)]
isl_tab: allow introduction of extra variables
Sven Verdoolaege [Wed, 5 Aug 2009 08:08:04 +0000 (10:08 +0200)]
isl_tab: introduce parameters and divs
Sven Verdoolaege [Fri, 7 Aug 2009 09:39:50 +0000 (11:39 +0200)]
isl_tab.h: fix typo in comment
Sven Verdoolaege [Wed, 5 Aug 2009 07:46:00 +0000 (09:46 +0200)]
isl_tab: allow saving and restoring the complete basis
Sven Verdoolaege [Wed, 5 Aug 2009 07:37:07 +0000 (09:37 +0200)]
isl_tab: privately export some functionality
Sven Verdoolaege [Wed, 5 Aug 2009 07:25:40 +0000 (09:25 +0200)]
isl_tab: store undo argument in a union for future extensions
Sven Verdoolaege [Thu, 6 Aug 2009 10:35:46 +0000 (12:35 +0200)]
add isl_basic_set_sample_bounded
Sven Verdoolaege [Tue, 4 Aug 2009 15:17:26 +0000 (17:17 +0200)]
privately export isl_basic_set_order_divs
Sven Verdoolaege [Tue, 4 Aug 2009 15:00:43 +0000 (17:00 +0200)]
isl_map_simplify.c: remove_dependent_vars: only remove definitions of divs
Don't remove the dependent divs themselves, because in particular
eliminate_divs_ineq does not expect any other divs to get removed.
Sven Verdoolaege [Mon, 3 Aug 2009 18:40:22 +0000 (20:40 +0200)]
isl_basic_map_compute_divs: use isl_basic_set_lexmin and move to isl_map.c
There is no need for the core of isl_basic_map_compute_divs to use any
piplib specific code. We therefore move the code to isl_map.c so
that it can also be used on top of another PILP solver.
Sven Verdoolaege [Mon, 3 Aug 2009 17:58:51 +0000 (19:58 +0200)]
isl_pip_basic_map_compute_divs: don't turn divs into output dimensions
There is no practical reason why we should want to do this transformation
and removing it makes it possible to you use the standard interface
to pip in the next commit.
Sven Verdoolaege [Mon, 3 Aug 2009 14:20:01 +0000 (16:20 +0200)]
privately export isl_basic_map_swap_div
Sven Verdoolaege [Mon, 3 Aug 2009 10:01:57 +0000 (12:01 +0200)]
isl_{set,map}_add: don't add obviously empty basic sets/maps
Sven Verdoolaege [Sun, 2 Aug 2009 17:46:30 +0000 (19:46 +0200)]
combine isl_pip_basic_map_lex{min,max} into isl_pip_basic_map_lexopt
Sven Verdoolaege [Sun, 2 Aug 2009 11:46:17 +0000 (13:46 +0200)]
make piplib headers private
Sven Verdoolaege [Sun, 2 Aug 2009 08:51:34 +0000 (10:51 +0200)]
isl_mat: keep track of the actual number of columns in a row
We need this number to perform extensions after dropping columns.
Sven Verdoolaege [Sat, 1 Aug 2009 17:32:04 +0000 (19:32 +0200)]
isl_tab_pivot: fix typo that prevented normalization of rows
Sven Verdoolaege [Wed, 29 Jul 2009 13:18:47 +0000 (15:18 +0200)]
add isl_basic_set_positive_orthant
Sven Verdoolaege [Wed, 29 Jul 2009 12:40:46 +0000 (14:40 +0200)]
add isl_basic_set_partial_lex{min,max}
Sven Verdoolaege [Wed, 29 Jul 2009 12:33:14 +0000 (14:33 +0200)]
rename isl_basic_map_lex{min,max} to isl_basic_map_partial_lex{min,max}
Sven Verdoolaege [Tue, 28 Jul 2009 14:21:42 +0000 (16:21 +0200)]
add isl_basic_set_free_div
Sven Verdoolaege [Tue, 28 Jul 2009 11:48:54 +0000 (13:48 +0200)]
isl_set_dim: support isl_dim_all
Sven Verdoolaege [Fri, 24 Jul 2009 15:47:35 +0000 (17:47 +0200)]
isl_tab: store index of variable in undo record instead of pointer to variable
The row of variables might get reallocated between pushing the undo
record and performing the undo, invalidating the pointer.
Sven Verdoolaege [Fri, 24 Jul 2009 10:22:14 +0000 (12:22 +0200)]
add isl_{set,map}_grow
Sven Verdoolaege [Sun, 2 Aug 2009 17:11:15 +0000 (19:11 +0200)]
add isl_map_get_dim
Sven Verdoolaege [Sun, 2 Aug 2009 17:05:36 +0000 (19:05 +0200)]
add isl_basic_map_get_dim
Sven Verdoolaege [Tue, 4 Aug 2009 17:39:23 +0000 (19:39 +0200)]
add isl_tab_dup
Sven Verdoolaege [Tue, 4 Aug 2009 17:33:09 +0000 (19:33 +0200)]
export isl_mat_dup
Sven Verdoolaege [Thu, 23 Jul 2009 16:51:26 +0000 (18:51 +0200)]
isl_tab.c: mark_redundant: only mark variable nonneg if they weren't already
More imporantly, don't undo such a mark during rollback.
Sven Verdoolaege [Thu, 23 Jul 2009 16:15:17 +0000 (18:15 +0200)]
isl_tab.c: to_row: allow pivoting in arbitrary direction
While undoing the allocation of a row, we may be dealing with
a row that was unbounded in both directions and is now in a column.
To move the column back to a row, we just pivot using any non-zero entry.
Sven Verdoolaege [Thu, 23 Jul 2009 13:29:44 +0000 (15:29 +0200)]
isl_tab.c: simplify code by letting mark_empty return tab
Sven Verdoolaege [Thu, 23 Jul 2009 09:46:25 +0000 (11:46 +0200)]
add isl_seq_last_non_zero
Sven Verdoolaege [Thu, 23 Jul 2009 09:40:43 +0000 (11:40 +0200)]
isl_tab.c: simplify add_eq
Sven Verdoolaege [Thu, 23 Jul 2009 07:24:41 +0000 (09:24 +0200)]
isl_tab.c: extract allocate_con
Sven Verdoolaege [Wed, 22 Jul 2009 11:39:26 +0000 (13:39 +0200)]
privately export isl_basic_set_set_rational
Sven Verdoolaege [Wed, 22 Jul 2009 19:35:40 +0000 (21:35 +0200)]
configure.ac: explicitly set AC_CONFIG_AUX_DIR
Without it, libtool can apparently get confused about which
ltmain.sh to use.
Sven Verdoolaege [Tue, 21 Jul 2009 11:37:22 +0000 (13:37 +0200)]
convex_hull: coalesce set during facet computation
Sven Verdoolaege [Tue, 21 Jul 2009 11:31:47 +0000 (13:31 +0200)]
isl_map_coalesce: don't drop rational flag from result if set in input
Sven Verdoolaege [Mon, 20 Jul 2009 19:46:14 +0000 (21:46 +0200)]
isl_tab_cone_is_bounded: start over after computing sign_of_max
sign_of_max may have made some rows redundant and may therefore
invalidate the iteration over all non-redundant rows.
Problem reported by Uday Kumar <udayreddy@gmail.com>
Sven Verdoolaege [Sat, 18 Jul 2009 16:06:02 +0000 (18:06 +0200)]
isl_basic_set_dim_residue_class: only set *modulo to 0 when dimension is fixed
Before, when no residue class could be detected, *modulo was sometimes
set to 0 and sometimes to 1. Now *modulo is always set to 1 in these
cases, except when the specified dimension has a fixed constant value,
in which case *modulo is set to 0 and *residue to the fixed value.
Sven Verdoolaege [Sat, 18 Jul 2009 16:00:14 +0000 (18:00 +0200)]
add isl_basic_set_fast_dim_is_fixed
Sven Verdoolaege [Thu, 16 Jul 2009 18:03:29 +0000 (20:03 +0200)]
isl_tab: drop isl_ctx argument where not absolutely required
Sven Verdoolaege [Thu, 16 Jul 2009 17:16:06 +0000 (19:16 +0200)]
isl_mat: keep track of isl_ctx
Sven Verdoolaege [Thu, 16 Jul 2009 09:00:32 +0000 (11:00 +0200)]
isl_basic_set_sample: don't project out lineality space up front
For the pip based sampler, projecting out the lineality space
is part of isl_basic_set_skew_to_positive_orthant, so there is
no need for a separate projection step before the skewing.
For the gbr based sampler, there is no need to project out the lineality
space. The lineality space will simply be part of the recession cone,
which is handled more efficiently than the projection.
In particular, for systems with many variables, the unimodular transformation
used in the projection may have very large coefficients, which in turn
leads to constraints with large coefficients. Since there is no need
to do this projection, it is best to avoid it.
Sven Verdoolaege [Wed, 15 Jul 2009 08:35:43 +0000 (10:35 +0200)]
isl_basic_map_fix_pos: micro-optimization
Sven Verdoolaege [Tue, 14 Jul 2009 13:34:00 +0000 (15:34 +0200)]
move isl_basic_set_skew_to_positive_orthant to isl_sample.c
Also, replace independent_bounds in isl_sample.c by that
of isl_sample_piplib.c
The difference is that the latter returns affine bounds
rather than linear bounds and that it return the actual
bounds from the set rather than some linear combinations
of bounds.
It is usually better to use the original bounds as
the linearly transformed bounds may have bigger coefficients
and may therefore be more difficult to process.
Sven Verdoolaege [Mon, 13 Jul 2009 15:02:37 +0000 (17:02 +0200)]
isl_tab.c: fix typo in comment
Sven Verdoolaege [Mon, 13 Jul 2009 10:23:49 +0000 (12:23 +0200)]
isl_basic_set_sample: break early if sample found in basic_set_range
Sven Verdoolaege [Mon, 13 Jul 2009 09:49:43 +0000 (11:49 +0200)]
export isl_tab_sample_is_integer
Sven Verdoolaege [Mon, 13 Jul 2009 09:23:06 +0000 (11:23 +0200)]
isl_basic_set_sample: check sample stored by isl_basic_map_is_empty first
Sven Verdoolaege [Mon, 13 Jul 2009 09:22:10 +0000 (11:22 +0200)]
isl_basic_map_is_empty: remove stale sample
Sven Verdoolaege [Mon, 15 Jun 2009 10:02:54 +0000 (12:02 +0200)]
add isl_polyhedron_sample application
Sven Verdoolaege [Mon, 15 Jun 2009 10:02:54 +0000 (12:02 +0200)]
introduce generalized basis reduction based sampling
Also make gbr the default for computing sample integer points.
It may be a bit slower than pip on easy problems, but pip can
sometimes get into serious problems, especially in cases where
the given set does not contain any integer points. The gbr
method performs much better in these cases.
Sven Verdoolaege [Wed, 15 Jul 2009 09:00:18 +0000 (11:00 +0200)]
add isl_seq_cdiv_q
Sven Verdoolaege [Sun, 12 Jul 2009 10:30:49 +0000 (12:30 +0200)]
isl_sample.c: interval_sample: drop redundant argument
Sven Verdoolaege [Sun, 12 Jul 2009 16:47:58 +0000 (18:47 +0200)]
isl_sample.c: clean up handling of lineality space
Sven Verdoolaege [Sun, 12 Jul 2009 09:43:03 +0000 (11:43 +0200)]
isl_sample.c: extract out sample_eq
Sven Verdoolaege [Sun, 12 Jul 2009 09:16:34 +0000 (11:16 +0200)]
isl_sample.c: interval_sample: handle equalities directly
Sven Verdoolaege [Sun, 12 Jul 2009 08:47:22 +0000 (10:47 +0200)]
isl_sample.c: extract out empty_sample
Sven Verdoolaege [Sat, 11 Jul 2009 17:56:06 +0000 (19:56 +0200)]
isl_sample.c: generalize point_sample to zero_sample
Sven Verdoolaege [Sat, 11 Jul 2009 13:40:41 +0000 (15:40 +0200)]
isl_tab: don't create new undo records during rollback
Sven Verdoolaege [Sat, 11 Jul 2009 13:33:25 +0000 (15:33 +0200)]
isl_tab_min: use general rollback mechanism
Sven Verdoolaege [Sat, 11 Jul 2009 13:15:26 +0000 (15:15 +0200)]
isl_tab: optionally save dual solution
Sven Verdoolaege [Sat, 11 Jul 2009 12:26:15 +0000 (14:26 +0200)]
isl_tab: add isl_tab_add_valid_eq
Sven Verdoolaege [Sat, 11 Jul 2009 09:11:23 +0000 (11:11 +0200)]
export isl_tab_alloc
Sven Verdoolaege [Fri, 10 Jul 2009 16:00:48 +0000 (18:00 +0200)]
add isl_int_le
Sven Verdoolaege [Thu, 9 Jul 2009 14:20:47 +0000 (16:20 +0200)]
privately export isl_basic_set_recession_cone
Sven Verdoolaege [Thu, 9 Jul 2009 13:49:07 +0000 (15:49 +0200)]
isl_convex_hull.c: add missing assignment
Sven Verdoolaege [Thu, 9 Jul 2009 13:15:51 +0000 (15:15 +0200)]
privately export isl_basic_set_lineality_space
Sven Verdoolaege [Thu, 9 Jul 2009 09:16:41 +0000 (11:16 +0200)]
isl_vec: keep track of isl_ctx
Sven Verdoolaege [Sun, 12 Jul 2009 10:23:35 +0000 (12:23 +0200)]
isl_coalesce.c: fix typo
Sven Verdoolaege [Sat, 13 Jun 2009 11:20:54 +0000 (13:20 +0200)]
update piplib for change in configure arguments
Sven Verdoolaege [Mon, 25 May 2009 21:43:50 +0000 (23:43 +0200)]
isl_basic_map_drop_redundant_divs: coalesce divs if possible
Sven Verdoolaege [Fri, 22 May 2009 10:17:00 +0000 (12:17 +0200)]
isl_basic_map_drop_redundant_divs: set div expression if obvious from constraints
Sven Verdoolaege [Sat, 23 May 2009 11:59:32 +0000 (13:59 +0200)]
isl_basic_map_drop_redundant_divs: drop more kinds of redundant divs
Sven Verdoolaege [Fri, 22 May 2009 09:26:31 +0000 (11:26 +0200)]
isl_map_compute_divs: drop obviously redundant divs first
Sven Verdoolaege [Fri, 22 May 2009 09:18:26 +0000 (11:18 +0200)]
isl_map_piplib.c: extremum_on: detect equalities first
In a map with several divs, there may be some that are
actually equal to each other (up to a constant). Any
div present in the map will make the search for the
lexicographic maximum or minimum more difficult, so
we want to remove such duplicate divs before embarking
on the search.
This situation occurs especially during dependence
analysis (in an outside user of isl). Perhaps it
would be best if the outside user would attempt
to remove duplicate divs instead of doing it
indiscriminately inside the library, but for now
it is easiest to just put it here.
Sven Verdoolaege [Mon, 25 May 2009 10:59:23 +0000 (12:59 +0200)]
isl_pip_basic_map_compute_divs: remove some equalities first
Sven Verdoolaege [Sun, 24 May 2009 14:18:34 +0000 (16:18 +0200)]
isl_pip_basic_map_compute_divs: separate out dimension games
We want to do some additional transformations on the input
set and it is easier to perform these transformations
with the existential variables considered as output variables.
Sven Verdoolaege [Mon, 25 May 2009 10:10:38 +0000 (12:10 +0200)]
isl_basic_set_preimage: handle divs in input
Sven Verdoolaege [Sun, 7 Jun 2009 14:29:08 +0000 (16:29 +0200)]
isl_input_omega.c: make variable_{free,new} static
Sven Verdoolaege [Sun, 7 Jun 2009 14:24:47 +0000 (16:24 +0200)]
isl_map.c: make add_divs static
Sven Verdoolaege [Tue, 2 Jun 2009 13:05:56 +0000 (15:05 +0200)]
isl_basic_map_simplify: detect div constraints while looking for duplicates
During the detection of duplicate constraints we also look for pairs
of opposite constraints and these can potentially be used to define
a div.
Sven Verdoolaege [Fri, 22 May 2009 19:25:49 +0000 (21:25 +0200)]
isl_basic_map_drop: properly handle dimensions of type isl_dim_div
Sven Verdoolaege [Mon, 25 May 2009 14:40:27 +0000 (16:40 +0200)]
add isl_int_mul_ui
Sven Verdoolaege [Mon, 25 May 2009 15:06:22 +0000 (17:06 +0200)]
add isl_seq_fdiv_q
Sven Verdoolaege [Fri, 22 May 2009 10:33:20 +0000 (12:33 +0200)]
add isl_seq_fdiv_r