[PPL-devel] [GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: some little optimizations to find_lexico_minimum_column_in_set().

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at 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);
       }
     }