summaryrefslogtreecommitdiff
path: root/isl_sample.c
AgeCommit message (Collapse)AuthorFilesLines
2012-11-20isl_tab_sample: perform greedy search before performing basis reductionSven Verdoolaege1-2/+85
While basis reduction is very useful on difficult problems, it is overkill on easy problems. In fact, the basis reduction computation can be quite expensive, especially in the presence of large coefficients. This may happen in particular during the affine hull computation when only a few sample points have been found so far. If these points have large values, then the equalities that describe their affine hull may have coefficients with larger values still. Perform a greedy search before computing a reduced basis. We also perform a greedy search after computing the reduced basis just in case the problem has become easy through this basis reduction. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2012-11-20isl_tab_sample: extract out compute_min and compute_maxSven Verdoolaege1-9/+32
We will be able to reuse them in the next commit. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2012-11-20isl_tab_sample: treat emptiness of tableau as errorSven Verdoolaege1-12/+12
We only modify the tableau through calls to isl_tab_add_valid_eq, which should never result in an empty tableau, given that the tableau was initially not empty. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2012-09-02relicense isl under the MIT licenseSven Verdoolaege1-1/+1
Signed-off-by: Tobias Grosser <tobias@grosser.es> Signed-off-by: Andreas Kloeckner <kloeckner@cims.nyu.edu> Signed-off-by: Todor Stefanov <stefanov@liacs.nl> Signed-off-by: Sven van Haastregt <svhaastr@liacs.nl> Signed-off-by: Isabelle Ryl <isabelle.ryl@inria.fr> Signed-off-by: Mythri Alle <mythri.allel@gmail.com> Signed-off-by: Wim De Clercq <Wim.DeClercq@lrd.kuleuven.be> Signed-off-by: Anne Cormier <Anne.Cormier@ens.fr> Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2012-02-24add isl_basic_set_sampleSven Verdoolaege1-0/+5
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2012-01-16isl_tab_from_basic_map: preserve all constraints in input when trackingSven Verdoolaege1-4/+2
If the user wants to keep track of a basic map representation of the tableau, then we need to make sure that the initial tableau corresponds exactly to the input. In particular, we need to make sure that no (redundant) constraints are removed. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2011-11-13hide isl_options structureSven Verdoolaege1-0/+1
We also add some getters and setters for options that are known to be used from outside of isl. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2011-09-03rename isl_dim to isl_spaceSven Verdoolaege1-4/+4
The old name was confusing because the name suggested that the object represents a single dimension, while in fact it represents an entire space. The documented isl_dim based names are for backward compatibility. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2011-05-05rename *_fast_* functions to *_plain_*Sven Verdoolaege1-3/+3
Although the *_fast_* functions are certainly meant to be faster than their unqualified alternatives, they are faster only because they are not complete. The "plain" qualification is hopefully better at conveying the idea that these functions only consider the obvious cases. We keep some of the *_fast_* names for backward compatibility. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2011-04-21change isl_mat_sub_alloc prototypeSven Verdoolaege1-1/+1
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2011-03-16hide isl_ctx internalsSven Verdoolaege1-0/+1
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2011-01-27merge isl_basic_set/isl_basic_map and isl_set/isl_mapSven Verdoolaege1-1/+1
Internally, these are essentially the same. We do keep the distinction in the external interface. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2011-01-16isl_basic_set_sample_point: exploit factorization if anySven Verdoolaege1-0/+79
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2010-11-20Rename headers from isl_header.h to isl/header.hSven Verdoolaege1-3/+3
We need to turn on the nostdinc option of automake as otherwise it would include -I$(top_builddir)/include/isl in DEFAULT_INCLUDES because of AC_CONFIG_HEADERS(include/isl/config.h) in configure.ac. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2010-10-26rename isl_map_remove to isl_map_remove_dimsSven Verdoolaege1-1/+2
The new name is more consistent with other functions and avoids confusion as to what is being added. Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2010-09-16merge isl_basic_set_drop_constraints_involving implementationsSven Verdoolaege1-23/+2
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
2010-06-26isl_tab_add_valid_eq: return int instead of isl_tab *Sven Verdoolaege1-1/+2
2010-06-26isl_sample.c: interval_sample: avoid NULL pointer dereferenceSven Verdoolaege1-0/+4
2010-06-26isl_sample.c: drop_constraints_involving: avoid NULL pointer dereferenceSven Verdoolaege1-2/+2
2010-06-26isl_sample.c: gbr_sample: avoid NULL pointer dereferenceSven Verdoolaege1-0/+5
2010-06-12isl_tab_detect_implicit_equalities: return integer instead of struct isl_tab *Sven Verdoolaege1-3/+2
2010-04-10isl_sample.c: initial_basis: set n_unbounded and n_zeroSven Verdoolaege1-1/+2
n_unbounded and n_zero are initialized to zero, but they can be set to non-zero values in isl_tab_set_initial_basis_with_cone. If isl_tab_sample is later called on an updated tab, but with the old basis removed, then these values, in particular n_unbounded, may not be valid anymore. In particular, this happens in isl_tab_pip.c's gbr_get_sample. Arguably, gbr_get_sample should reset the values of n_zero and n_unbounded when it drops the basis, but it doens't hurt for initial_basis to reset those values too.
2010-03-04add isl_set_sample_pointSven Verdoolaege1-0/+39
2009-12-16add copyright statementsSven Verdoolaege1-0/+9
2009-12-07isl_tab: keep track of isl_basic_map instead of isl_basic_setSven Verdoolaege1-5/+13
2009-11-29isl_tab_add_ineq and isl_tab_mark_empty: return status instead of isl_tab *Sven Verdoolaege1-2/+3
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.
2009-10-21put options in a separate isl_options structureSven Verdoolaege1-13/+14
2009-10-12isl_tab: improved error handlingSven Verdoolaege1-1/+2
2009-10-10add isl_tab_set_initial_basis_with_coneSven Verdoolaege1-0/+126
2009-10-09isl_basic_map_detect_equalities: keep track of sampleSven Verdoolaege1-1/+1
2009-10-09isl_tab_sample: handle unbounded directions in initial basisSven Verdoolaege1-4/+47
2009-10-09exploit equalities in isl_tab_sampleSven Verdoolaege1-7/+87
2009-10-09isl_tab_sample: be more verbose about unbounded directionsSven Verdoolaege1-2/+4
2009-10-09separate out isl_tab_sample from sample_boundedSven Verdoolaege1-44/+85
2009-10-09sample_bounded: reimplement to work directly on a tableauSven Verdoolaege1-205/+113
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.
2009-10-09isl_tab_compute_reduced_basis: work with affine basis instead of linear basisSven Verdoolaege1-1/+0
2009-10-08isl_sample.c: basic_set_sample: remember boundedness of basic setSven Verdoolaege1-1/+2
2009-10-07isl_sample.c: basic_set_reduced: fix typo preventing use of gbr_only_firstSven Verdoolaege1-1/+1
2009-10-07privately export isl_basic_set_sample_with_coneSven Verdoolaege1-3/+3
2009-09-14add isl_basic_map_sample and isl_map_sampleSven Verdoolaege1-0/+53
2009-09-13isl_sample.c: move isl_basic_set_from_vec from isl_affine_hull.cSven Verdoolaege1-0/+34
2009-09-13rename isl_basic_set_sample to isl_basic_set_sample_vecSven Verdoolaege1-2/+2
2009-09-13make some internal functions staticSven Verdoolaege1-1/+1
2009-08-28export isl_vec_ceilSven Verdoolaege1-18/+0
2009-08-28isl_basic_set_sample: only perform basis reduction onceSven Verdoolaege1-2/+12
On larger problem, much time was spent on repeated basis reductions with little or no reduction on the number of points visited. The initial basis reduction seems to be sufficient in most cases.
2009-08-07add isl_basic_set_sample_boundedSven Verdoolaege1-2/+15
2009-07-16isl_tab: drop isl_ctx argument where not absolutely requiredSven Verdoolaege1-10/+10
2009-07-16isl_mat: keep track of isl_ctxSven Verdoolaege1-48/+38
2009-07-16isl_basic_set_sample: don't project out lineality space up frontSven Verdoolaege1-87/+24
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.
2009-07-15move isl_basic_set_skew_to_positive_orthant to isl_sample.cSven Verdoolaege1-9/+103
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.
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-19 10:30:13 +0000