Module: ppl/ppl Branch: sparse_matrices Commit: 0a92d18cae3f6b93a4e8d3209269962b45407558 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0a92d18cae3f6...

Author: Marco Poletti poletti.marco@gmail.com Date: Fri Mar 12 14:15:48 2010 +0100

PIP_Tree.cc: some little optimizations to find_lexico_minimum_column_in_set().

---

src/PIP_Tree.cc | 26 ++++++++++++-------------- 1 files changed, 12 insertions(+), 14 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 491a6e3..18d9dc5 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -440,16 +440,11 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, new_candidates.insert(*i); dimension_type min_column = *i; ++i; + const Coefficient* sij_b = &(pivot_row.get(min_column)); for ( ; i!=i_end; ++i) { const Coefficient& sij_a = pivot_row.get(*i); - const Coefficient& sij_b = pivot_row.get(min_column); PPL_ASSERT(sij_a > 0); - PPL_ASSERT(sij_b > 0); - - PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff); - PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff); - lhs_coeff = -sij_b; - rhs_coeff = -sij_a; + PPL_ASSERT(*sij_b > 0);

PPL_DIRTY_TEMP_COEFFICIENT(lhs); PPL_DIRTY_TEMP_COEFFICIENT(rhs); @@ -461,19 +456,19 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, // Reconstitute the identity submatrix part of tableau. if (mk == *i) { // Optimizing for: lhs == lhs_coeff && rhs == 0; - if (lhs_coeff == 0) + if (*sij_b == 0) new_candidates.insert(*i); else { - if (lhs_coeff > 0) + if (*sij_b < 0) found_better_candidate = true; } } if (mk == min_column) { // Optimizing for: lhs == 0 && rhs == rhs_coeff; - if (rhs_coeff == 0) + if (sij_a == 0) new_candidates.insert(*i); else { - if (0 > rhs_coeff) + if (0 < sij_a) found_better_candidate = true; } } @@ -485,18 +480,21 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, const Coefficient* t_mk_ja; const Coefficient* t_mk_jb; t_mk.get2(*i,min_column,t_mk_ja,t_mk_jb); - lhs = lhs_coeff * *t_mk_ja; - rhs = rhs_coeff * *t_mk_jb; + // lhs is actually the left-hand side with toggled sign. + // rhs is actually the left-hand side with toggled sign. + lhs = *sij_b * *t_mk_ja; + rhs = sij_a * *t_mk_jb; if (lhs == rhs) new_candidates.insert(*i); else { - if (lhs > rhs) + if (lhs < rhs) found_better_candidate = true; } } if (found_better_candidate) { new_candidates.clear(); min_column = *i; + sij_b = &sij_a; new_candidates.insert(min_column); } }