March 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Drafted the implementation of methods drop_some_non_integer_points().
by Roberto Bagnara 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: master Commit: ce7681699c3e6056ce77eb9492ae8a051bb00dc3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ce7681699c3e… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Wed Mar 24 21:37:52 2010 +0400 Drafted the implementation of methods drop_some_non_integer_points(). --- src/Polyhedron.defs.hh | 18 ++++++ src/Polyhedron.inlines.hh | 13 ++++ src/Polyhedron_nonpublic.cc | 135 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 166 insertions(+), 0 deletions(-) diff --git a/src/Polyhedron.defs.hh b/src/Polyhedron.defs.hh index 3a1f563..0a3c86b 100644 --- a/src/Polyhedron.defs.hh +++ b/src/Polyhedron.defs.hh @@ -2698,6 +2698,24 @@ protected: //@} // Exception Throwers #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) + /*! \brief + Possibly tightens \p *this by dropping some points with non-integer + coordinates for the space dimensions corresponding to \p *pvars. + + \param pvars + When nonzero, points with non-integer coordinates for the + variables/space-dimensions contained in \p *pvars can be discarded. + + \param complexity + The maximal complexity of any algorithms used. + + \note + Currently there is no optimality guarantee, not even if + \p complexity is <CODE>ANY_COMPLEXITY</CODE>. + */ + void drop_some_non_integer_points(const Variables_Set* pvars, + Complexity_Class complexity); + //! Helper function that overapproximates an interval linear form. /*! \param lf diff --git a/src/Polyhedron.inlines.hh b/src/Polyhedron.inlines.hh index 8f3aeef..2909057 100644 --- a/src/Polyhedron.inlines.hh +++ b/src/Polyhedron.inlines.hh @@ -431,6 +431,19 @@ Polyhedron::strictly_contains(const Polyhedron& y) const { return x.contains(y) && !y.contains(x); } +inline void +Polyhedron::drop_some_non_integer_points(Complexity_Class complexity) { + drop_some_non_integer_points(static_cast<const Variables_Set*>(0), + complexity); +} + +inline void +Polyhedron::drop_some_non_integer_points(const Variables_Set& vars, + Complexity_Class complexity) { + drop_some_non_integer_points(&vars, complexity); +} + + namespace Interfaces { inline bool diff --git a/src/Polyhedron_nonpublic.cc b/src/Polyhedron_nonpublic.cc index 1cd9fb2..a54c639 100644 --- a/src/Polyhedron_nonpublic.cc +++ b/src/Polyhedron_nonpublic.cc @@ -2075,6 +2075,141 @@ PPL::Polyhedron::BFT00_poly_hull_assign_if_exact(const Polyhedron& y) { } void +PPL::Polyhedron::drop_some_non_integer_points(const Variables_Set* pvars, + Complexity_Class complexity) { + // There is nothing to do for an empty set of variables. + if (pvars != 0 && pvars->empty()) + return; + + // Any empty polyhedron does not contain integer points. + if (marked_empty()) + return; + + // A zero-dimensional, universe polyhedron has, by convention, an + // integer point. + if (space_dim == 0) + set_empty(); + + // The constraints (possibly with pending rows) are required. + if (has_pending_generators()) { + // Processing of pending generators is exponential in the worst case. + if (complexity != ANY_COMPLEXITY) + return; + else + process_pending_generators(); + } + if (!constraints_are_up_to_date()) { + // Constraints update is exponential in the worst case. + if (complexity != ANY_COMPLEXITY) + return; + else + update_constraints(); + } + + PPL_ASSERT(!has_pending_generators() && constraints_are_up_to_date()); + + bool changed = false; + const dimension_type eps_index = space_dim + 1; + PPL_DIRTY_TEMP_COEFFICIENT(gcd); + + for (dimension_type j = con_sys.num_rows(); j-- > 0; ) { + Constraint& c = con_sys[j]; + if (c.is_tautological()) + goto next_constraint; + + if (pvars != 0) { + for (dimension_type i = space_dim; i-- > 0; ) + if (c[i+1] != 0 && pvars->find(i) == pvars->end()) + goto next_constraint; + } + + if (!is_necessarily_closed()) { + // Transform all strict inequalities into non-strict ones, + // with the inhomogeneous term incremented by 1. + if (c[eps_index] < 0 && !c.is_tautological()) { + c[eps_index] = 0; + ++c[0]; + changed = true; + } + } + + { + // Compute the GCD of all the homogeneous terms. + dimension_type i = space_dim+1; + while (i > 1) { + const Coefficient& c_i = c[--i]; + if (const int c_i_sign = sgn(c_i)) { + gcd = c_i; + if (c_i_sign < 0) + neg_assign(gcd); + goto compute_gcd; + } + } + // We reach this point only if all the coefficients were zero. + goto maybe_normalize; + + compute_gcd: + if (gcd == 1) + goto maybe_normalize; + while (i > 1) { + const Coefficient& c_i = c[--i]; + if (c_i != 0) { + // See the comment in Row::normalize(). + gcd_assign(gcd, c_i, gcd); + if (gcd == 1) + goto maybe_normalize; + } + } + PPL_ASSERT(gcd != 1); + PPL_ASSERT(c[0] % gcd != 0); + + // If we have an equality, the polyhedron becomes empty. + if (c.is_equality()) { + set_empty(); + return; + } + + // Divide the inhomogeneous coefficients by the GCD. + for (dimension_type i = space_dim+1; --i > 0; ) { + Coefficient& c_i = c[i]; + exact_div_assign(c_i, c_i, gcd); + } + Coefficient& c_0 = c[0]; + const int c_0_sign = sgn(c_0); + c_0 /= gcd; + if (c_0_sign < 0) + --c_0; + changed = true; + } + + maybe_normalize: + if (changed) + // Enforce normalization. + //c.normalize(); + ; + + next_constraint: + ; + } + + if (changed) { + if (!is_necessarily_closed()) { + con_sys.insert(Constraint::epsilon_leq_one()); + // FIXME: make sure that the following line really can stay here + // and should not be moved below the brace. + con_sys.set_sorted(false); + } + + // After changing the system of constraints, the generators + // are no longer up-to-date and the constraints are no longer + // minimized. + clear_generators_up_to_date(); + clear_constraints_minimized(); + } + PPL_ASSERT_HEAVY(OK()); +} + +void PPL::Polyhedron::throw_runtime_error(const char* method) const { std::ostringstream s; s << "PPL::";

1 0

[GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row_Std_Vector_Backend: add and use sequential_search_treshold.
by Marco Poletti 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: f3957a85aeb8243fe82d015780a17d7601126865 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f3957a85aeb8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 24 16:24:38 2010 +0100 Unlimited_Sparse_Row_Std_Vector_Backend: add and use sequential_search_treshold. --- ...Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh | 5 +++++ ...imited_Sparse_Row_Std_Vector_Backend.inlines.hh | 18 ++++++++++++++++++ 2 files changed, 23 insertions(+), 0 deletions(-) diff --git a/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh b/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh index a479672..370feba 100644 --- a/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh +++ b/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh @@ -57,6 +57,11 @@ private: Unlimited_Sparse_Row_Std_Vector_Backend::key_value_comparison<Compare> key_value_compare(const Compare& comp); + //! This is the number of sequential comparisons after which binary search + //! is performed. This affects performance, but not correctness. + //! Some methods do one more comparison. + static const dimension_type sequential_search_treshold = 3; + public: //! Needed to satisfy the backend requirements. //! This is not a typedef to allow overloading of methods with both types. diff --git a/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh b/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh index c7c8776..02f3696 100644 --- a/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh +++ b/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh @@ -143,6 +143,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::dangerous_iterator Unlimited_Sparse_Row_Std_Vector_Backend ::lower_bound_dangerous(const dimension_type k, dangerous_iterator itr) { PPL_ASSERT(itr == end_dangerous() || (*itr).first <= k); + for (dimension_type i = sequential_search_treshold; i-- > 0; ) { + if (itr == end_dangerous() || (*itr).first >= k) + return itr; + ++itr; + } + // Now perform binary search. return std::lower_bound(itr, end_dangerous(), k, value_key_compare(std::less<dimension_type>())); } @@ -162,6 +168,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::iterator Unlimited_Sparse_Row_Std_Vector_Backend ::lower_bound(const dimension_type k, iterator itr) { PPL_ASSERT(itr == end() || (*itr).first <= k); + for (dimension_type i = sequential_search_treshold; i-- > 0; ) { + if (itr == end() || (*itr).first >= k) + return itr; + ++itr; + } + // Now perform binary search. return std::lower_bound(itr, end(), k, value_key_compare(std::less<dimension_type>())); } @@ -181,6 +193,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::const_iterator Unlimited_Sparse_Row_Std_Vector_Backend ::lower_bound(const dimension_type k, const_iterator itr1) const { PPL_ASSERT(itr1 == end() || (*itr1).first <= k); + for (dimension_type i = sequential_search_treshold; i-- > 0; ) { + if (itr1 == end() || (*itr1).first >= k) + return itr1; + ++itr1; + } + // Now perform binary search. return std::lower_bound(itr1, end(), k, value_key_compare(std::less<dimension_type>())); }

1 0

[GIT] ppl/ppl(master): Enable the interfaces procedures for Grid:: drop_some_non_integer_points().
by Patricia Hill 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: master Commit: 44bb8667fb1c413b18a1a504425200b246254f00 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=44bb8667fb1c… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Wed Mar 24 14:31:43 2010 +0000 Enable the interfaces procedures for Grid::drop_some_non_integer_points(). --- ...erface_generator_common_procedure_generators.m4 | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/interfaces/ppl_interface_generator_common_procedure_generators.m4 b/interfaces/ppl_interface_generator_common_procedure_generators.m4 index f83a37d..81fa8ad 100644 --- a/interfaces/ppl_interface_generator_common_procedure_generators.m4 +++ b/interfaces/ppl_interface_generator_common_procedure_generators.m4 @@ -90,8 +90,8 @@ ppl_@CLASS@_remove_higher_space_dimensions/2 *nofail +all, ppl_@CLASS@_expand_space_dimension/3 *nofail +all, ppl_@CLASS@_fold_space_dimensions/3 +all, ppl_@CLASS@_map_space_dimensions/2 +all, -ppl_@CLASS@_drop_some_non_integer_points/2 +simple -polyhedron -grid, -ppl_@CLASS@_drop_some_non_integer_points_2/3 +simple -polyhedron -grid, +ppl_@CLASS@_drop_some_non_integer_points/2 +simple -polyhedron, +ppl_@CLASS@_drop_some_non_integer_points_2/3 +simple -polyhedron, ppl_@CLASS@_ascii_dump/1 +all, ppl_@CLASS@_@MEMBYTES@/2 +all, dnl

1 0

[GIT] ppl/ppl(master): Added a draft implementation for Grid:: drop_some_non_integer_points().
by Patricia Hill 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: master Commit: 94e1497598ab744385a8447a0df714dc9156ade5 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=94e1497598ab… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Wed Mar 24 14:27:29 2010 +0000 Added a draft implementation for Grid::drop_some_non_integer_points(). --- src/Grid_public.cc | 55 ++++++ tests/Grid/Makefile.am | 1 + tests/Grid/dropnonintegerpoints1.cc | 322 +++++++++++++++++++++++++++++++++++ 3 files changed, 378 insertions(+), 0 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=94e14975…

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: use std::vector instead of std ::set in find_lexico_minimum_column().
by Marco Poletti 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 54ade0980f342b457c2fb9daa9a9a2764d8d95db URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=54ade0980f34… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 24 14:45:17 2010 +0100 PIP_Tree.cc: use std::vector instead of std::set in find_lexico_minimum_column(). --- src/PIP_Tree.cc | 27 +++++++++++++++------------ 1 files changed, 15 insertions(+), 12 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index ed775ea..c838a45 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -346,7 +346,7 @@ column_lower(const PIP_Tree_Node::matrix_type& tableau, index(es). */ void -find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, +find_lexico_minimum_column_in_set(std::vector<dimension_type>& candidates, const PIP_Tree_Node::matrix_type& tableau, const std::vector<dimension_type>& mapping, const std::vector<bool>& basis, @@ -355,12 +355,14 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, const dimension_type num_vars = mapping.size(); PPL_ASSERT(!candidates.empty()); + // This is used as a set, it is always sorted. + std::vector<dimension_type> new_candidates; for (dimension_type var_index = 0; var_index < num_vars; ++var_index) { - std::set<dimension_type> new_candidates; - std::set<dimension_type>::const_iterator i = candidates.begin(); - std::set<dimension_type>::const_iterator i_end = candidates.end(); + new_candidates.clear(); + std::vector<dimension_type>::const_iterator i = candidates.begin(); + std::vector<dimension_type>::const_iterator i_end = candidates.end(); PPL_ASSERT(!candidates.empty()); - new_candidates.insert(*i); + new_candidates.push_back(*i); dimension_type min_column = *i; ++i; if (i == i_end) @@ -391,10 +393,10 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, new_candidates.clear(); min_column = *i; sij_b = &sij_a; - new_candidates.insert(min_column); + new_candidates.push_back(min_column); } else // Optimizing for: lhs == 0 && rhs == 0; - new_candidates.insert(*i); + new_candidates.push_back(*i); } } } else { @@ -440,7 +442,7 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, min_column = *i; row_jb = row_ja; sij_b = &sij_a; - new_candidates.insert(min_column); + new_candidates.push_back(min_column); } } else { // lhs is actually the left-hand side with toggled sign. @@ -448,14 +450,14 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, lhs = *sij_b * *row_ja; rhs = sij_a * *row_jb; if (lhs == rhs) - new_candidates.insert(*i); + new_candidates.push_back(*i); else if (lhs < rhs) { new_candidates.clear(); min_column = *i; row_jb = row_ja; sij_b = &sij_a; - new_candidates.insert(min_column); + new_candidates.push_back(min_column); } } } @@ -477,11 +479,12 @@ find_lexico_minimum_column(const PIP_Tree_Node::matrix_type& tableau, const dimension_type start_j, dimension_type& j_out) { const dimension_type num_cols = tableau.num_columns(); - std::set<dimension_type> candidates; + // This is used as a set, it is always sorted. + std::vector<dimension_type> candidates; for (dimension_type j = start_j; j < num_cols; ++j) { const Coefficient& c = pivot_row[j]; if (c > 0) - candidates.insert(j); + candidates.push_back(j); } if (candidates.empty()) { j_out = num_cols;

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: use std::vector instead of std ::set in compatibility_check_find_pivot().
by Marco Poletti 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 39b6702613942db58c897b824d36c7feb2f340a5 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=39b670261394… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 24 14:39:36 2010 +0100 PIP_Tree.cc: use std::vector instead of std::set in compatibility_check_find_pivot(). --- src/PIP_Tree.cc | 29 ++++++++++++++++------------- 1 files changed, 16 insertions(+), 13 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 012a46a..ed775ea 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -540,7 +540,7 @@ struct compatibility_check_find_pivot_map_data { }; void -compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, +compatibility_check_find_pivot_in_set(std::vector<std::pair<dimension_type, compatibility_check_find_pivot_map_data > >& candidates, const PIP_Tree_Node::matrix_type& s, @@ -548,12 +548,13 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, mapping, const std::vector<bool>& basis) { typedef compatibility_check_find_pivot_map_data map_data; - typedef std::set<std::pair<dimension_type, map_data> > candidates_t; + typedef std::vector<std::pair<dimension_type, map_data> > candidates_t; + // This is used as a set, it is always sorted. + candidates_t new_candidates; const dimension_type num_vars = mapping.size(); for (dimension_type var_index = 0; var_index < num_vars; ++var_index) { const dimension_type row_index = mapping[var_index]; const bool in_base = basis[var_index]; - candidates_t new_candidates; candidates_t::const_iterator i = candidates.begin(); candidates_t::const_iterator i_end = candidates.end(); PPL_ASSERT(i != i_end); @@ -561,7 +562,8 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, dimension_type pj = i->first; const Coefficient* cost = i->second.cost; const Coefficient* value = i->second.value; - new_candidates.insert(*i); + new_candidates.clear(); + new_candidates.push_back(*i); if (in_base) { for (++i; i != i_end; ++i) { bool found_better_pivot = false; @@ -583,19 +585,19 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, if (row_index == pj) { // Optimizing for: lhs == lhs_coeff && rhs == 0; if (lhs_coeff_sgn == 0) - new_candidates.insert(*i); + new_candidates.push_back(*i); else found_better_pivot = lhs_coeff_sgn > 0; } else { if (row_index == challenger_j) { // Optimizing for: lhs == 0 && rhs == rhs_coeff; if (rhs_coeff_sgn == 0) - new_candidates.insert(*i); + new_candidates.push_back(*i); else found_better_pivot = 0 > rhs_coeff_sgn; } else // Optimizing for: lhs == 0 && rhs == 0; - new_candidates.insert(*i); + new_candidates.push_back(*i); } if (found_better_pivot) { pi = challenger_i; @@ -603,7 +605,7 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, cost = challenger_cost; value = challenger_value; new_candidates.clear(); - new_candidates.insert(*i); + new_candidates.push_back(*i); } } } else { @@ -660,7 +662,7 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, value = challenger_value; row_value = row_challenger_value; new_candidates.clear(); - new_candidates.insert(*i); + new_candidates.push_back(*i); } } else { @@ -675,7 +677,7 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, rhs *= *row_challenger_value; if (lhs == rhs) - new_candidates.insert(*i); + new_candidates.push_back(*i); else { if (lhs > rhs) { pi = challenger_i; @@ -684,7 +686,7 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, value = challenger_value; row_value = row_challenger_value; new_candidates.clear(); - new_candidates.insert(*i); + new_candidates.push_back(*i); } } } @@ -705,7 +707,8 @@ compatibility_check_find_pivot(const PIP_Tree_Node::matrix_type& s, // maximizing pivot column. const dimension_type num_rows = s.num_rows(); typedef compatibility_check_find_pivot_map_data map_data; - typedef std::set<std::pair<dimension_type, map_data> > candidates_t; + // This is used as a set, it is always sorted. + typedef std::vector<std::pair<dimension_type, map_data> > candidates_t; typedef std::map<dimension_type,map_data> candidates_map_t; candidates_map_t candidates_map; for (dimension_type i = 0; i < num_rows; ++i) { @@ -774,7 +777,7 @@ compatibility_check_find_pivot(const PIP_Tree_Node::matrix_type& s, candidates_map_t::iterator i = candidates_map.begin(); candidates_map_t::iterator i_end = candidates_map.end(); for ( ; i != i_end; ++i) - candidates.insert(*i); + candidates.push_back(*i); if (!candidates.empty()) { compatibility_check_find_pivot_in_set(candidates, s, mapping, basis); PPL_ASSERT(!candidates.empty());

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node::Tableau: remove useless calls to get() in is_better_pivot().
by Marco Poletti 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 1e08d6d4fe52090c88785d04d46f6e12e627289e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1e08d6d4fe52… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 24 14:30:35 2010 +0100 PIP_Solution_Node::Tableau: remove useless calls to get() in is_better_pivot(). --- src/PIP_Tree.cc | 12 +++++++----- 1 files changed, 7 insertions(+), 5 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 3370301..012a46a 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1529,15 +1529,17 @@ PIP_Solution_Node::Tableau for ( ; j != j_end; ++j) coeff_1[(*j).first] = (*j).second * s_0_0; } + matrix_row_const_iterator j0 = t_0.end(); + matrix_row_const_iterator j0_end = t_0.end(); + matrix_row_const_iterator j1 = t_1.end(); + matrix_row_const_iterator j1_end = t_1.end(); for (dimension_type i = 0; i < num_rows; ++i) { matrix_row_const_reference_type s_i = s[i]; const Coefficient* s_i_col_0; const Coefficient* s_i_col_1; s_i.get2(col_0, col_1, s_i_col_0, s_i_col_1); - matrix_row_const_iterator j0 = t_0.begin(); - matrix_row_const_iterator j0_end = t_0.end(); - matrix_row_const_iterator j1 = t_1.begin(); - matrix_row_const_iterator j1_end = t_1.end(); + j0 = t_0.begin(); + j1 = t_1.begin(); while (j0 != j0_end && j1 != j1_end) { if ((*j0).first == (*j1).first) { product_0 = (*j0).second * s_1_1 * *s_i_col_0; @@ -1587,7 +1589,7 @@ PIP_Solution_Node::Tableau end_loop: return (j_mismatch != num_params) && column_lower(s, mapping, basis, s_0, col_0, s_1, col_1, - t_0.get(j_mismatch), t_1.get(j_mismatch)); + (*j0).second, (*j1).second); } void

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: optimize generate_cut() method for sparse matrices.
by Marco Poletti 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: df30069d54bac2910ae48614bb4c664a7034924f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=df30069d54ba… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 24 14:20:07 2010 +0100 PIP_Solution_Node: optimize generate_cut() method for sparse matrices. --- src/PIP_Tree.cc | 11 +++++++++-- 1 files changed, 9 insertions(+), 2 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 7fea489..3370301 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -3321,8 +3321,15 @@ PIP_Solution_Node::generate_cut(const dimension_type index, matrix_row_const_reference_type row_s = tableau.s[index]; matrix_row_const_reference_type row_t = tableau.t[index]; { - for (dimension_type j = 0; j < num_vars; ++j) { - mod_assign(cut_s[j], row_s[j], den); + matrix_row_const_iterator j = row_s.begin(); + matrix_row_const_iterator j_end = row_s.end(); + if (j != j_end) { + matrix_row_iterator itr = cut_s.find_create((*j).first); + mod_assign((*itr).second, (*j).second, den); + for (++j; j != j_end; ++j) { + itr = cut_s.find_create((*j).first, itr); + mod_assign((*itr).second, (*j).second, den); + } } } {

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: modify generate_cut() to be efficient even with backends that have slow insertions.
by Marco Poletti 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: f5cfe2cc744d52668839b3e0d67dc37fc90448fc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f5cfe2cc744d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 24 14:12:34 2010 +0100 PIP_Solution_Node: modify generate_cut() to be efficient even with backends that have slow insertions. --- src/PIP_Tree.cc | 26 ++++++++++++++++++++++---- 1 files changed, 22 insertions(+), 4 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b35d093..7fea489 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -3238,6 +3238,28 @@ PIP_Solution_Node::generate_cut(const dimension_type index, matrix_const_row_const_iterator j_end = row_t.end(); matrix_row_iterator itr1 = ctx1.end(); matrix_row_iterator itr2 = ctx2.end(); + if (j != j_end && (*j).first == 0) { + mod_assign(mod, (*j).second, den); + if (mod != 0) { + itr1 = ctx1.find_create(0, den); + (*itr1).second -= mod; + itr2 = ctx2.find_create(0, (*itr1).second); + neg_assign((*itr2).second); + // ctx2[0] += den-1; + (*itr2).second += den; + --(*itr2).second; + } else { + // ctx2[0] += den-1; + itr2 = ctx2.find_create(0,den); + --(*itr2).second; + } + ++j; + } else { + // ctx2[0] += den-1; + Coefficient& ctx2_0 = ctx2[0]; + ctx2_0 += den; + --ctx2_0; + } for ( ; j != j_end; ++j) { mod_assign(mod, (*j).second, den); if (mod != 0) { @@ -3272,10 +3294,6 @@ PIP_Solution_Node::generate_cut(const dimension_type index, ctx2.find_create(num_params ,den); } } - // ctx2[0] += den-1; - Coefficient& ctx2_0 = ctx2[0]; - ctx2_0 += den; - --ctx2_0; #ifdef NOISY_PIP { using namespace IO_Operators;

1 0

[GIT] ppl/ppl(master): Added the generated Termination files to make clean.
by Patricia Hill 24 Mar '10

24 Mar '10

Module: ppl/ppl Branch: master Commit: 70025f8ab031445a6f590ab92dbc7e43fc8b24af URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=70025f8ab031… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Wed Mar 24 12:23:10 2010 +0000 Added the generated Termination files to make clean. --- .../Java/parma_polyhedra_library/Makefile.am | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-) diff --git a/interfaces/Java/parma_polyhedra_library/Makefile.am b/interfaces/Java/parma_polyhedra_library/Makefile.am index 73c0afa..2f59201 100644 --- a/interfaces/Java/parma_polyhedra_library/Makefile.am +++ b/interfaces/Java/parma_polyhedra_library/Makefile.am @@ -217,6 +217,7 @@ $(fixed_java_cxx_headers_sources) \ java_classes.stamp \ java_cxx_headers.stamp \ source_generation.stamp \ +Termination.java \ Bounded_Integer_Type_Overflow.class \ Bounded_Integer_Type_Representation.class \ Bounded_Integer_Type_Width.class \ @@ -259,6 +260,7 @@ Poly_Con_Relation.class \ Poly_Gen_Relation.class \ PPL_Object.class \ Relation_Symbol.class \ +Termination.class \ Timeout_Exception.class \ Variable.class \ Variables_Set.class

1 0