[PPL-devel] [GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: optimize solve() method for sparse matrices.
Marco Poletti
poletti.marco at gmail.com
Sun Mar 14 21:50:13 CET 2010
Module: ppl/ppl
Branch: sparse_matrices
Commit: d7f564d11a7a3343632642df26e702047f076d23
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d7f564d11a7a3343632642df26e702047f076d23
Author: Marco Poletti <poletti.marco at gmail.com>
Date: Sun Mar 14 20:42:16 2010 +0100
PIP_Solution_Node: optimize solve() method for sparse matrices.
---
src/PIP_Tree.cc | 98 +++++++++++++++++++++++++++++++++++-------------------
1 files changed, 63 insertions(+), 35 deletions(-)
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index c038176..c1f1cdf 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -2779,16 +2779,20 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
if (s_pivot_pj != pivot_den) {
for (dimension_type i = num_rows; i-- > 0; ) {
matrix_row_reference_type s_i = tableau.s[i];
- product = s_i[pj] * pivot_den;
- if (product % s_pivot_pj != 0) {
- // As above, perform matrix scaling.
- gcd_assign(gcd, product, s_pivot_pj);
- exact_div_assign(scale_factor, s_pivot_pj, gcd);
- tableau.scale(scale_factor);
- product *= scale_factor;
+ matrix_row_iterator itr = s_i.find(pj);
+ if (itr != s_i.end()) {
+ Coefficient& s_i_pj = (*itr).second;
+ product = s_i_pj * pivot_den;
+ if (product % s_pivot_pj != 0) {
+ // As above, perform matrix scaling.
+ gcd_assign(gcd, product, s_pivot_pj);
+ exact_div_assign(scale_factor, s_pivot_pj, gcd);
+ tableau.scale(scale_factor);
+ product *= scale_factor;
+ }
+ PPL_ASSERT(product % s_pivot_pj == 0);
+ exact_div_assign(s_i_pj, product, s_pivot_pj);
}
- PPL_ASSERT(product % s_pivot_pj == 0);
- exact_div_assign(s_i[pj], product, s_pivot_pj);
}
}
@@ -2814,20 +2818,28 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
continue;
// No positive variable coefficient.
bool has_positive = false;
- matrix_row_const_reference_type s_i = tableau.s[i];
- for (dimension_type j = 0; j < num_vars; ++j)
- if (s_i[j] > 0) {
- has_positive = true;
- break;
- }
+ {
+ matrix_row_const_reference_type s_i = tableau.s[i];
+ matrix_const_row_const_iterator j = s_i.begin();
+ matrix_const_row_const_iterator j_end = s_i.end();
+ for ( ; j!=j_end; ++j)
+ if ((*j).second > 0) {
+ has_positive = true;
+ break;
+ }
+ }
if (has_positive)
continue;
// Minimize parameter coefficient score,
// eliminating implicated tautologies (if any).
matrix_row_const_reference_type t_i = tableau.t[i];
score = 0;
- for (dimension_type j = num_params; j-- > 0; )
- score += t_i[j];
+ {
+ matrix_const_row_const_iterator j = t_i.begin();
+ matrix_const_row_const_iterator j_end = t_i.end();
+ for ( ; j!=j_end; ++j)
+ score += (*j).second;
+ }
if (i_neg == not_a_dim || score < best_score) {
i_neg = i;
best_score = score;
@@ -2857,8 +2869,12 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
continue;
matrix_row_const_reference_type t_i = tableau.t[i];
score = 0;
- for (dimension_type j = num_params; j-- > 0; )
- score += t_i[j];
+ {
+ matrix_const_row_const_iterator j = t_i.begin();
+ matrix_const_row_const_iterator j_end = t_i.end();
+ for ( ; j!=j_end; ++j)
+ score += (*j).second;
+ }
if (best_i == not_a_dim || score < best_score) {
best_score = score;
best_i = i;
@@ -2869,11 +2885,11 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
t_test.normalize();
#ifdef NOISY_PIP
{
- Linear_Expression expr = Linear_Expression(t_test[0]);
+ Linear_Expression expr = Linear_Expression(t_test.get(0));
dimension_type j = 1;
for (Variables_Set::const_iterator p = all_params.begin(),
p_end = all_params.end(); p != p_end; ++p, ++j)
- expr += t_test[j] * Variable(*p);
+ expr += t_test.get(j) * Variable(*p);
using namespace IO_Operators;
std::cerr << "Found mixed parameter sign row: " << best_i << ".\n"
<< "Solution depends on sign of parameter "
@@ -2982,8 +2998,10 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
continue;
const dimension_type i = mapping[k];
matrix_row_const_reference_type t_i = tableau.t[i];
- for (dimension_type j = num_params; j-- > 0; ) {
- if (t_i[j] % den != 0)
+ matrix_const_row_const_iterator j = t_i.begin();
+ matrix_const_row_const_iterator j_end = t_i.end();
+ for ( ; j!=j_end; ++j) {
+ if ((*j).second % den != 0)
goto non_integer;
}
}
@@ -3011,8 +3029,10 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
matrix_row_const_reference_type t_i = tableau.t[i];
// Count the number of non-integer parameter coefficients.
dimension_type pcount = 0;
- for (dimension_type j = num_params; j-- > 0; ) {
- mod_assign(mod, t_i[j], den);
+ matrix_const_row_const_iterator j = t_i.begin();
+ matrix_const_row_const_iterator j_end = t_i.end();
+ for ( ; j!=j_end; ++j) {
+ mod_assign(mod, (*j).second, den);
if (mod != 0)
++pcount;
}
@@ -3043,21 +3063,29 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
score = 0;
dimension_type pcount = 0;
matrix_row_const_reference_type t_i = tableau.t[i];
- for (dimension_type j = num_params; j-- > 0; ) {
- mod_assign(mod, t_i[j], den);
- if (mod != 0) {
- score += den;
- score -= mod;
- ++pcount;
+ {
+ matrix_const_row_const_iterator j = t_i.begin();
+ matrix_const_row_const_iterator j_end = t_i.end();
+ for ( ; j!=j_end; ++j) {
+ mod_assign(mod, (*j).second, den);
+ if (mod != 0) {
+ score += den;
+ score -= mod;
+ ++pcount;
+ }
}
}
// Compute s_score.
s_score = 0;
matrix_row_const_reference_type s_i = tableau.s[i];
- for (dimension_type j = num_vars; j-- > 0; ) {
- mod_assign(mod, s_i[j], den);
- s_score += den;
- s_score -= mod;
+ {
+ matrix_const_row_const_iterator j = s_i.begin();
+ matrix_const_row_const_iterator j_end = s_i.end();
+ for ( ; j!=j_end; ++j) {
+ mod_assign(mod, (*j).second, den);
+ s_score += den;
+ s_score -= mod;
+ }
}
// Combine 'score' and 's_score'.
score *= s_score;
More information about the PPL-devel
mailing list