Module: ppl/ppl Branch: sparse_matrices Commit: 8611bb81ec29979c5b5c3c4b95437a615888eab6 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8611bb81ec299...
Author: Marco Poletti poletti.marco@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); }