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

Author: Marco Poletti poletti.marco@gmail.com Date: Wed Mar 17 23:07:59 2010 +0100

PIP_Problem: optimize solve() method for sparse matrices.

---

src/PIP_Problem.cc | 49 +++++++++++++++++++++++++++++++++++++++---------- 1 files changed, 39 insertions(+), 10 deletions(-)

diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index f1191be..3eca9e7 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -155,20 +155,49 @@ PPL::PIP_Problem::solve() const {

// Translate constraint into context row. matrix_row_copy_type row(new_num_cols); - row[0] = c.inhomogeneous_term(); { + matrix_row_copy_iterator itr = row.end(); + + if (c.inhomogeneous_term() != 0) { + itr = row.find_create(0,c.inhomogeneous_term()); + // Adjust inhomogenous term if strict. + if (c.is_strict_inequality()) + --((*itr).second); + } else { + // Adjust inhomogenous term if strict. + if (c.is_strict_inequality()) + itr = row.find_create(0,-1); + } dimension_type i = 1; - for (Variables_Set::const_iterator - pi = param_begin; pi != param_end; ++pi, ++i) { - if (*pi < c_space_dim) - row[i] = c.coefficient(Variable(*pi)); - else - break; + bool continue_looping = true; + Variables_Set::const_iterator pi = param_begin; + + if (itr == row.end()) + for ( ; pi != param_end; ++pi, ++i) { + if (*pi < c_space_dim) { + const Coefficient& x = c.coefficient(Variable(*pi)); + if (x != 0) { + itr = row.find_create(i,x); + // itr is now initialized, use it in the next iterations. + ++pi; + ++i; + break; + } + } else + continue_looping = false; + } + if (continue_looping) { + for ( ; pi != param_end; ++pi, ++i) { + PPL_ASSERT(itr != row.end()); + if (*pi < c_space_dim) { + const Coefficient& x = c.coefficient(Variable(*pi)); + if (x != 0) + itr = row.find_create(i,x); + } else + break; + } } } - // Adjust inhomogenous term if strict. - if (c.is_strict_inequality()) - --row[0];

// Insert new row into initial context. x.initial_context.add_row(row);