[PPL-devel] [GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization.

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Fri Mar 12 13:37:16 2010 +0100

PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization.

---

 src/PIP_Tree.cc |   69 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 66 insertions(+), 3 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index b0ead97..0d0d95d 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -435,10 +435,73 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates,
   PPL_ASSERT(!candidates.empty());
   dimension_type min_index = *i;
   ++i;
-  for ( ; i!=i_end; ++i)
-    if (column_lower(tableau, mapping, basis,
-                     pivot_row, *i, pivot_row, min_index))
+  for ( ; i!=i_end; ++i) {
+    bool found_better_candidate;
+    const Coefficient& sij_a = pivot_row.get(*i);
+    const Coefficient& sij_b = pivot_row.get(min_index);
+    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_DIRTY_TEMP_COEFFICIENT(lhs);
+    PPL_DIRTY_TEMP_COEFFICIENT(rhs);
+    const dimension_type num_vars = mapping.size();
+    dimension_type k = 0;
+    // While loop guard is: (k < num_rows && lhs == rhs).
+    // Return value is false, if k >= num_rows; lhs < rhs, otherwise.
+    // Try to optimize the computation of lhs and rhs.
+    while (true) {
+      const dimension_type mk = mapping[k];
+      const bool in_base = basis[k];
+      if (++k >= num_vars) {
+        found_better_candidate = false;
+        break;
+      }
+      if (in_base) {
+        // Reconstitute the identity submatrix part of tableau.
+        if (mk == *i) {
+          // Optimizing for: lhs == lhs_coeff && rhs == 0;
+          if (lhs_coeff == 0)
+            continue;
+          else {
+            found_better_candidate = lhs_coeff > 0;
+            break;
+          }
+        }
+        if (mk == min_index) {
+          // Optimizing for: lhs == 0 && rhs == rhs_coeff;
+          if (rhs_coeff == 0)
+            continue;
+          else {
+            found_better_candidate = 0 > rhs_coeff;
+            break;
+          }
+        }
+        // Optimizing for: lhs == 0 && rhs == 0;
+        continue;
+      } else {
+        // Not in base.
+        PIP_Tree_Node::matrix_row_const_reference_type t_mk = tableau[mk];
+        const Coefficient* t_mk_ja;
+        const Coefficient* t_mk_jb;
+        t_mk.get2(*i,min_index,t_mk_ja,t_mk_jb);
+        lhs = lhs_coeff * *t_mk_ja;
+        rhs = rhs_coeff * *t_mk_jb;
+        if (lhs == rhs)
+          continue;
+        else {
+          found_better_candidate = lhs > rhs;
+          break;
+        }
+      }
+    }
+    if (found_better_candidate)
       min_index = *i;
+  }
   candidates.clear();
   candidates.insert(min_index);
 }