March 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(products): Merge branch 'master' into products
by Roberto Bagnara 15 Mar '10

15 Mar '10

Module: ppl/ppl Branch: products Commit: c68101c16e7f364d363b801448fa15b33088ed7c URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c68101c16e7f… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Mon Mar 15 15:53:22 2010 +0400 Merge branch 'master' into products ---

1 0

[GIT] ppl/ppl(products): Documentation fixes. Added a paragraph about optimizing a linear cost function.
by François Galea 15 Mar '10

15 Mar '10

Module: ppl/ppl Branch: products Commit: 6060bda39a0fb7b5d8d114d436b81a5a5b1eb74e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6060bda39a0f… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Mar 11 19:58:03 2010 +0100 Documentation fixes. Added a paragraph about optimizing a linear cost function. --- src/PIP_Problem.defs.hh | 42 +++++++++++++++++++++++++++++++----------- 1 files changed, 31 insertions(+), 11 deletions(-) diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 4def1e5..32920d9 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -323,33 +323,53 @@ operator<<(std::ostream& s, const PIP_Problem& p); which we will call \f$M\f$. - Reformulate each of the maximization problem constraints by substituting each \f$x_i\f$ variable with an expression of the form - \f$M-x'_i\f$, where the \f$x'_i\f$ variables are to be minimized. + \f$M-x'_i\f$, where the \f$x'_i\f$ variables are positive variables to + be minimized. - Solve the lexicographic minimum for the \f$x'\f$ variable vector. - - In the solution expressions, substitute each \f$x'_i\f$ variable back - to \f$M-x_i\f$. - + - In the solution expressions, the values of the original variables are + obtained from the resulting values of the \f$x'_i\f$ variables by + applying the equality \f$x_i = M-x'_i\f$. + \par You can choose to maximize only a subset of the variables while minimizing the other variables. In that case, just apply the variable substitution method on the variables you want to be maximized. The variable optimization priority will still be in lexicographic order. - \par Allowing variables to be arbitrarily signed - You can deal with arbitrarily signed variables by reformulating the - constraints using variable substitution. Proceed the following steps: + \par Allowing variables and parameters to be arbitrarily signed + You can deal with arbitrarily signed variables and/or parameters by + reformulating the constraints using variable and/or parameter + substitution. Proceed the following steps: - Create a big parameter (see PIP_Problem::set_big_parameter_dimension), which we will call \f$M\f$. - Reformulate each of the maximization problem constraints by substituting each \f$x_i\f$ variable with an expression of the form - \f$M+x'_i\f$, where the \f$x'_i\f$ variables are positive. + \f$x'_i-M\f$, where the \f$x'_i\f$ variables are positive, and/or by + substituting each \f$p_i\f$ parameter with an expression of the form + \f$p'_i-M\f$, where the \f$p'_i\f$ parameters are positive. - Solve the lexicographic minimum for the \f$x'\f$ variable vector. - - In the solution expressions, substitute each \f$x'_i\f$ variable back - to \f$x_i-M\f$. + - In the solution expressions, the values of the original variables + and/or parameters are obtained from the resulting values of the + \f$x'_i\f$ variables and/or the \f$p'_i\f$ parameters by applying the + equalities \f$x_i = M-x'_i\f$ and/or \f$p_i = M-p'_i\f$. + \par You can choose to define only a subset of the variables to be sign-unrestricted. In that case, just apply the variable substitution method on the variables you want to be sign-unrestricted. - FIXME: Solving problems with arbitrarily signed parameters + \par Minimizing a linear cost function + Lexicographic solving can be used to find the parametric minimum of a + linear cost function. + \par + Suppose the variables are named \f$x_1, x_2, \dots, x_n\f$, and the + parameters \f$p_1, p_2, \dots, p_m\f$. You can minimize a linear cost + function \f$f(x_2, \dots, x_n, p_1, \dots, p_m)\f$ by simply adding the + constraint \f$x_1 \geq f(x_2, \dots, x_n, p_1, \dots, p_m)\f$ to the + constraint system. As lexicographic minimization ensures \f$x_1\f$ is + minimized in priority, and because \f$x_1\f$ is forced by a constraint to + be superior or equal to the cost function, optimal solutions of the + problem necessarily ensure that the solution value of \f$x_1\f$ is the + optimal value of the cost function. */ class Parma_Polyhedra_Library::PIP_Problem { public:

1 0

[GIT] ppl/ppl(products): Improved checks in PIP_Decision_Node::OK() method.
by Enea Zaffanella 15 Mar '10

15 Mar '10

Module: ppl/ppl Branch: products Commit: ed91bdf10a46c8a1c886a2f05986e4d90db5f136 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ed91bdf10a46… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 18:29:05 2010 +0100 Improved checks in PIP_Decision_Node::OK() method. There is no reason to have Artificial_Parameter::OK() inlined. Added a couple of comments on code that should be normally unreachable. --- src/PIP_Tree.cc | 141 ++++++++++++++++++++++++++++------------------- src/PIP_Tree.inlines.hh | 13 ---- 2 files changed, 85 insertions(+), 69 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 79d254e..f2a06dc 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -332,6 +332,18 @@ PIP_Tree_Node::Artificial_Parameter return !operator==(y); } +bool +PIP_Tree_Node::Artificial_Parameter::OK() const { + if (denom <= 0) { +#ifndef NDEBUG + std::cerr << "PIP_Tree_Node::Artificial_Parameter " + << "has a non-positive denominator.\n"; +#endif + return false; + } + return true; +} + void PIP_Tree_Node::Artificial_Parameter::ascii_dump(std::ostream& s) const { s << "artificial_parameter "; @@ -639,8 +651,6 @@ PIP_Solution_Node::OK() const { bool PIP_Decision_Node::OK() const { - /* FIXME: finish me! */ - // Perform base class well-formedness check on this node. if (!PIP_Tree_Node::OK()) return false; @@ -651,6 +661,14 @@ PIP_Decision_Node::OK() const { if (true_child && !true_child->OK()) return false; + // Decision nodes should always have a true child. + if (!true_child) { +#ifndef NDEBUG + std::cerr << "PIP_Decision_Node with no 'true' child.\n"; +#endif + return false; + } + // Decision nodes with a false child must have exactly one constraint. if (false_child) { dimension_type @@ -717,59 +735,59 @@ PIP_Decision_Node::solve(const PIP_Problem& pip, context_false, all_params, space_dim); } - if (true_child != 0 || false_child != 0) { - PIP_Tree_Node* node = this; - if (has_false_child && false_child == 0) { - // False child has become unfeasible: merge this node's artificials with - // the true child, while removing the local parameter constraints, which - // are no longer discriminative. + if (true_child == 0 && false_child == 0) { + // No childs: the whole subtree is unfeasible. + delete this; + return 0; + } + + PIP_Tree_Node* node = this; + if (has_false_child && false_child == 0) { + // False child has become unfeasible: merge this node's artificials with + // the true child, while removing the local parameter constraints, which + // are no longer discriminative. + true_child->parent_merge(); + true_child->set_parent(parent()); + node = true_child; + true_child = 0; + delete this; + } + else if (has_true_child && true_child == 0) { + // True child has become unfeasible: merge this node's artificials + // with the false child. + false_child->parent_merge(); + false_child->set_parent(parent()); + node = false_child; + false_child = 0; + delete this; + } + else if (check_feasible_context) { + // Test all constraints for redundancy with the context, and eliminate + // them if not necessary. + Constraint_System cs; + cs.swap(constraints_); + const Constraint_System::const_iterator end = cs.end(); + for (Constraint_System::const_iterator ci = cs.begin(); ci != end; ++ci) { + Matrix ctx_copy(context); + merge_assign(ctx_copy, Constraint_System(*ci), all_params); + Row& last = ctx_copy[ctx_copy.num_rows()-1]; + complement_assign(last, last, 1); + if (compatibility_check(ctx_copy)) { + // The constraint is not redundant with the context: we must keep it. + constraints_.insert(*ci); + } + } + // If the constraints set has become empty, only keep the true child. + if (constraints_.empty()) { true_child->parent_merge(); true_child->set_parent(parent()); node = true_child; true_child = 0; delete this; } - else if (has_true_child && true_child == 0) { - // True child has become unfeasible: merge this node's artificials - // with the false child. - false_child->parent_merge(); - false_child->set_parent(parent()); - node = false_child; - false_child = 0; - delete this; - } - else if (check_feasible_context) { - // Test all constraints for redundancy with the context, and eliminate - // them if not necessary. - Constraint_System cs; - cs.swap(constraints_); - const Constraint_System::const_iterator end = cs.end(); - for (Constraint_System::const_iterator ci = cs.begin(); ci != end; ++ci) { - Matrix ctx_copy(context); - merge_assign(ctx_copy, Constraint_System(*ci), all_params); - Row& last = ctx_copy[ctx_copy.num_rows()-1]; - complement_assign(last, last, 1); - if (compatibility_check(ctx_copy)) { - // The constraint is not redundant with the context: we must keep it. - constraints_.insert(*ci); - } - } - // If the constraints set has become empty, only keep the true child. - if (constraints_.empty()) { - true_child->parent_merge(); - true_child->set_parent(parent()); - node = true_child; - true_child = 0; - delete this; - } - } - PPL_ASSERT(node->OK()); - return node; - } - else { - delete this; - return 0; } + PPL_ASSERT(node->OK()); + return node; } void @@ -779,8 +797,12 @@ PIP_Decision_Node::ascii_dump(std::ostream& s) const { // Dump true child (if any). s << "\ntrue_child: "; - if (true_child == 0) + if (true_child == 0) { + // Note: this branch should normally be unreachable code, since a + // well-formed decision node always has a true child. We keep this code + // for debugging purposes (since we want to dump broken nodes). s << "BOTTOM\n"; + } else if (const PIP_Decision_Node* dec = true_child->as_decision()) { s << "DECISION\n"; dec->ascii_dump(s); @@ -797,6 +819,11 @@ PIP_Decision_Node::ascii_dump(std::ostream& s) const { if (false_child == 0) s << "BOTTOM\n"; else if (const PIP_Decision_Node* dec = false_child->as_decision()) { + // Note: this branch should normally be unreachable code. + // Since a well-formed decision node having a false child should have + // a single context constraint, its false child will have no context + // constraints at all, so that no further branch is possible. + // We keep this code for debugging purposes. s << "DECISION\n"; dec->ascii_dump(s); } @@ -826,6 +853,7 @@ PIP_Decision_Node::ascii_load(std::istream& s) { if (!(s >> str)) return false; if (str == "BOTTOM") + // Note: normally unreachable code (see comment on ascii_dump). true_child = 0; else if (str == "DECISION") { PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0, 0); @@ -855,6 +883,7 @@ PIP_Decision_Node::ascii_load(std::istream& s) { if (str == "BOTTOM") false_child = 0; else if (str == "DECISION") { + // Note: normally unreachable code (see comment on ascii_dump). PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0, 0); false_child = dec; if (!dec->ascii_load(s)) @@ -1015,7 +1044,8 @@ PIP_Tree_Node::ascii_load(std::istream& s) { artificial_parameters.push_back(ap); } - PPL_ASSERT(OK()); + // Note: do not assert OK() here. + // The node invariants should be checked on derived nodes. return true; } @@ -1055,6 +1085,7 @@ PIP_Solution_Node::Tableau::ascii_load(std::istream& st) { return false; if (!t.ascii_load(st)) return false; + PPL_ASSERT(OK()); return true; } @@ -2502,8 +2533,8 @@ PIP_Tree_Node::external_memory_in_bytes() const { memory_size_type PIP_Decision_Node::external_memory_in_bytes() const { memory_size_type n = PIP_Tree_Node::external_memory_in_bytes(); - if (true_child) - n += true_child->total_memory_in_bytes(); + PPL_ASSERT(true_child != 0); + n += true_child->total_memory_in_bytes(); if (false_child) n += false_child->total_memory_in_bytes(); return n; @@ -2610,10 +2641,8 @@ PIP_Decision_Node::print_tree(std::ostream& s, unsigned indent, // Then print info specific of decision nodes. dimension_type child_first_art_dim = first_art_dim + art_parameter_count(); - if (true_child) - true_child->print_tree(s, indent+1, pip_dim_is_param, child_first_art_dim); - else - indent_and_print(s, indent+1, "_|_\n"); + PPL_ASSERT(true_child != 0); + true_child->print_tree(s, indent+1, pip_dim_is_param, child_first_art_dim); indent_and_print(s, indent, "else\n"); diff --git a/src/PIP_Tree.inlines.hh b/src/PIP_Tree.inlines.hh index 18a27d0..159b5c1 100644 --- a/src/PIP_Tree.inlines.hh +++ b/src/PIP_Tree.inlines.hh @@ -102,19 +102,6 @@ PIP_Decision_Node::child_node(bool v) { return v ? true_child : false_child; } - -inline bool -PIP_Tree_Node::Artificial_Parameter::OK() const { - if (denom <= 0) { -#ifndef NDEBUG - std::cerr << "PIP_Tree_Node::Artificial_Parameter " - << "has a non-positive denominator.\n"; -#endif - return false; - } - return true; -} - inline PIP_Tree_Node::Artificial_Parameter::Artificial_Parameter() : Linear_Expression(), denom(1) {

1 0

[GIT] ppl/ppl(products): Fixed documentation reference.
by Enea Zaffanella 15 Mar '10

15 Mar '10

Module: ppl/ppl Branch: products Commit: 61b4c1817137f7ffcf2d996e1aee6aea4f32d2bf URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=61b4c1817137… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 18:27:08 2010 +0100 Fixed documentation reference. --- interfaces/C/ppl_c_header.h | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index 403a3ce..d899321 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -734,7 +734,7 @@ PPL_TYPE_DECLARATION(PIP_Solution_Node) The types and functions for PIP artificial parameters provide an interface towards - \extref{Parma_Polyhedra_Library::Artificial_Parameter, Artificial_Parameter}. + \extref{Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter, Artificial_Parameter}. */ PPL_TYPE_DECLARATION(Artificial_Parameter) PPL_TYPE_DECLARATION(Artificial_Parameter_Sequence)

1 0

[GIT] ppl/ppl(products): Fixed the value of INPUT doxygen configuration variable.
by Enea Zaffanella 15 Mar '10

15 Mar '10

Module: ppl/ppl Branch: products Commit: 374f46632936ca58d8da878da73ac5f28f09a666 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=374f46632936… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 17:14:26 2010 +0100 Fixed the value of INPUT doxygen configuration variable. --- doc/devref.doxyconf-html.in | 8 +++++--- doc/devref.doxyconf-latex.in | 8 +++++--- 2 files changed, 10 insertions(+), 6 deletions(-) diff --git a/doc/devref.doxyconf-html.in b/doc/devref.doxyconf-html.in index 052c850..5c45175 100644 --- a/doc/devref.doxyconf-html.in +++ b/doc/devref.doxyconf-html.in @@ -152,6 +152,7 @@ INPUT = @srcdir@/definitions.dox \ @srcdir@/../src/MIP_Problem.types.hh \ @srcdir@/../src/MIP_Problem.defs.hh \ @srcdir@/../src/MIP_Problem.inlines.hh \ + @srcdir@/../src/MIP_Problem.templates.hh \ @srcdir@/../src/MIP_Problem.cc \ @srcdir@/../src/Bit_Row.types.hh \ @srcdir@/../src/Bit_Row.defs.hh \ @@ -317,14 +318,15 @@ INPUT = @srcdir@/definitions.dox \ @srcdir@/../src/Octagonal_Shape.inlines.hh \ @srcdir@/../src/Octagonal_Shape.templates.hh \ @srcdir@/../src/Octagonal_Shape.cc \ - @srcdir@/../src/PIP_Problem.cc \ + @srcdir@/../src/PIP_Problem.types.hh \ @srcdir@/../src/PIP_Problem.defs.hh \ @srcdir@/../src/PIP_Problem.inlines.hh \ @srcdir@/../src/PIP_Problem.templates.hh \ - @srcdir@/../src/PIP_Problem.types.hh \ + @srcdir@/../src/PIP_Problem.cc \ + @srcdir@/../src/PIP_Tree.types.hh \ @srcdir@/../src/PIP_Tree.defs.hh \ @srcdir@/../src/PIP_Tree.inlines.hh \ - @srcdir@/../src/PIP_Tree.types.hh \ + @srcdir@/../src/PIP_Tree.cc \ @srcdir@/../src/Floating_Point_Expression.types.hh \ @srcdir@/../src/Floating_Point_Expression.defs.hh \ @srcdir@/../src/Floating_Point_Expression.inlines.hh \ diff --git a/doc/devref.doxyconf-latex.in b/doc/devref.doxyconf-latex.in index 5d1545d..f1be5a8 100644 --- a/doc/devref.doxyconf-latex.in +++ b/doc/devref.doxyconf-latex.in @@ -152,6 +152,7 @@ INPUT = @srcdir@/definitions.dox \ @srcdir@/../src/MIP_Problem.types.hh \ @srcdir@/../src/MIP_Problem.defs.hh \ @srcdir@/../src/MIP_Problem.inlines.hh \ + @srcdir@/../src/MIP_Problem.templates.hh \ @srcdir@/../src/MIP_Problem.cc \ @srcdir@/../src/Bit_Row.types.hh \ @srcdir@/../src/Bit_Row.defs.hh \ @@ -317,14 +318,15 @@ INPUT = @srcdir@/definitions.dox \ @srcdir@/../src/Octagonal_Shape.inlines.hh \ @srcdir@/../src/Octagonal_Shape.templates.hh \ @srcdir@/../src/Octagonal_Shape.cc \ - @srcdir@/../src/PIP_Problem.cc \ + @srcdir@/../src/PIP_Problem.types.hh \ @srcdir@/../src/PIP_Problem.defs.hh \ @srcdir@/../src/PIP_Problem.inlines.hh \ @srcdir@/../src/PIP_Problem.templates.hh \ - @srcdir@/../src/PIP_Problem.types.hh \ + @srcdir@/../src/PIP_Problem.cc \ + @srcdir@/../src/PIP_Tree.types.hh \ @srcdir@/../src/PIP_Tree.defs.hh \ @srcdir@/../src/PIP_Tree.inlines.hh \ - @srcdir@/../src/PIP_Tree.types.hh \ + @srcdir@/../src/PIP_Tree.cc \ @srcdir@/../src/Floating_Point_Expression.types.hh \ @srcdir@/../src/Floating_Point_Expression.defs.hh \ @srcdir@/../src/Floating_Point_Expression.inlines.hh \

1 0

[GIT] ppl/ppl(products): Conflicts resolved.
by Patricia Hill 15 Mar '10

15 Mar '10

Module: ppl/ppl Branch: products Commit: 8760df47483200e17daf43df3c7ca4ec7aad9185 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8760df474832… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Mon Mar 15 11:18:15 2010 +0000 Conflicts resolved. --- src/Partially_Reduced_Product.templates.hh | 9 --------- 1 files changed, 0 insertions(+), 9 deletions(-) diff --git a/src/Partially_Reduced_Product.templates.hh b/src/Partially_Reduced_Product.templates.hh index 0626970..174a57d 100644 --- a/src/Partially_Reduced_Product.templates.hh +++ b/src/Partially_Reduced_Product.templates.hh @@ -254,10 +254,7 @@ Partially_Reduced_Product<D1, D2, R> if (is_empty()) return false; -<<<<<<< HEAD:src/Partially_Reduced_Product.templates.hh -======= PPL_ASSERT(reduced); ->>>>>>> master:src/Partially_Reduced_Product.templates.hh PPL_DIRTY_TEMP_COEFFICIENT(inf1_n); PPL_DIRTY_TEMP_COEFFICIENT(inf1_d); @@ -310,10 +307,7 @@ Partially_Reduced_Product<D1, D2, R> if (is_empty()) return false; -<<<<<<< HEAD:src/Partially_Reduced_Product.templates.hh -======= PPL_ASSERT(reduced); ->>>>>>> master:src/Partially_Reduced_Product.templates.hh PPL_DIRTY_TEMP_COEFFICIENT(sup1_n); PPL_DIRTY_TEMP_COEFFICIENT(sup1_d); @@ -372,10 +366,7 @@ Partially_Reduced_Product<D1, D2, R> if (is_empty()) return false; -<<<<<<< HEAD:src/Partially_Reduced_Product.templates.hh -======= PPL_ASSERT(reduced); ->>>>>>> master:src/Partially_Reduced_Product.templates.hh PPL_DIRTY_TEMP_COEFFICIENT(inf1_n); PPL_DIRTY_TEMP_COEFFICIENT(inf1_d);

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: optimize update_solution () method for sparse matrices.
by Marco Poletti 14 Mar '10

14 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: b57748fb891db5dffb5befcda20d153c8dbd6846 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b57748fb891d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 21:24:36 2010 +0100 PIP_Solution_Node: optimize update_solution() method for sparse matrices. --- src/PIP_Tree.cc | 13 ++++++++----- 1 files changed, 8 insertions(+), 5 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 1fc81d3..8e470b2 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -3647,16 +3647,19 @@ PIP_Solution_Node continue; matrix_row_const_reference_type row = tableau.t[mapping[i]]; - for (dimension_type j = num_all_params; j-- > 0; ) { - // NOTE: add 1 to column index to account for inhomogenous term. - const Coefficient& coeff = row[j+1]; + // Start from index 1 to skip the inhomogenous term. + matrix_const_row_const_iterator j = row.lower_bound(1); + matrix_const_row_const_iterator j_end = row.end(); + for ( ; j!=j_end; ++j) { + const Coefficient& coeff = (*j).second; if (coeff == 0) continue; norm_coeff = coeff / den; if (norm_coeff != 0) - add_mul_assign(sol_i, norm_coeff, Variable(all_param_names[j])); + add_mul_assign(sol_i, norm_coeff, + Variable(all_param_names[(*j).first-1])); } - norm_coeff = row[0] / den; + norm_coeff = row.get(0) / den; sol_i += norm_coeff; }

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: optimize generate_cut() method for sparse matrices.
by Marco Poletti 14 Mar '10

14 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 65bee8a4e2b4bd9c833c6c420447fb5d4e1bea37 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=65bee8a4e2b4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 21:17:46 2010 +0100 PIP_Solution_Node: optimize generate_cut() method for sparse matrices. --- src/PIP_Tree.cc | 136 +++++++++++++++++++++++++++++++++++++++---------------- 1 files changed, 97 insertions(+), 39 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index c1f1cdf..1fc81d3 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -3150,8 +3150,10 @@ PIP_Solution_Node::generate_cut(const dimension_type index, { // Limiting the scope of reference row_t (may be later invalidated). matrix_row_const_reference_type row_t = tableau.t[index]; - for (dimension_type j = 1; j < num_params; ++j) - if (row_t[j] % den != 0) { + matrix_const_row_const_iterator j = row_t.lower_bound(1); + matrix_const_row_const_iterator j_end = row_t.end(); + for ( ; j!=j_end; ++j) + if ((*j).second % den != 0) { generate_parametric_cut = true; break; } @@ -3168,24 +3170,32 @@ PIP_Solution_Node::generate_cut(const dimension_type index, // Limiting the scope of reference row_t (may be later invalidated). { matrix_row_const_reference_type row_t = tableau.t[index]; - mod_assign(mod, row_t[0], den); + mod_assign(mod, row_t.get(0), den); if (mod != 0) { // Optimizing computation: expr += (den - mod); expr += den; expr -= mod; } - // NOTE: iterating downwards on parameters to avoid reallocations. - Variables_Set::const_reverse_iterator p_j = parameters.rbegin(); - // NOTE: index j spans [1..num_params-1] downwards. - for (dimension_type j = num_params; j-- > 1; ) { - mod_assign(mod, row_t[j], den); - if (mod != 0) { - // Optimizing computation: expr += (den - mod) * Variable(*p_j); - coeff = den - mod; - add_mul_assign(expr, coeff, Variable(*p_j)); + if (!parameters.empty()) { + // To avoid reallocations of expr. + add_mul_assign(expr, 0, Variable(*(parameters.rbegin()))); + Variables_Set::const_iterator p_j = parameters.begin(); + matrix_const_row_const_iterator j = row_t.lower_bound(1); + matrix_const_row_const_iterator j_end = row_t.end(); + dimension_type last_index; + if (j!=j_end) + last_index = (*j).first; + for ( ; j!=j_end; ++j) { + mod_assign(mod, (*j).second, den); + if (mod != 0) { + // Optimizing computation: expr += (den - mod) * Variable(*p_j); + coeff = den - mod; + PPL_ASSERT(last_index <= (*j).first); + std::advance(p_j,(*j).first - last_index); + last_index = (*j).first; + add_mul_assign(expr, coeff, Variable(*p_j)); + } } - // Mode to previous parameter. - ++p_j; } } // Generate new artificial parameter. @@ -3239,28 +3249,58 @@ PIP_Solution_Node::generate_cut(const dimension_type index, matrix_row_reference_type ctx2 = context[ctx_num_rows+1]; // Recompute row reference after possible reallocation. matrix_row_const_reference_type row_t = tableau.t[index]; - for (dimension_type j = 0; j < num_params; ++j) { - mod_assign(mod, row_t[j], den); - if (mod != 0) { - ctx1[j] = den; - ctx1[j] -= mod; - neg_assign(ctx2[j], ctx1[j]); + { + matrix_const_row_const_iterator j = row_t.begin(); + matrix_const_row_const_iterator j_end = row_t.end(); + matrix_row_iterator itr1 = ctx1.end(); + matrix_row_iterator itr2 = ctx2.end(); + for ( ; j!=j_end; ++j) { + mod_assign(mod, (*j).second, den); + if (mod != 0) { + const dimension_type j_index = (*j).first; + itr1 = ctx1.find_create(j_index,den); + (*itr1).second -= mod; + itr2 = ctx2.find_create(j_index,(*itr1).second); + neg_assign((*itr2).second); + // Now itr1 and itr2 are valid, so we can use them in the next + // calls to find_create(). + ++j; + break; + } + } + for ( ; j!=j_end; ++j) { + mod_assign(mod, (*j).second, den); + if (mod != 0) { + const dimension_type j_index = (*j).first; + itr1 = ctx1.find_create(j_index,den,itr1); + (*itr1).second -= mod; + itr2 = ctx2.find_create(j_index,(*itr1).second,itr2); + neg_assign((*itr2).second); + } + } + if (itr1 != ctx1.end()) { + itr1 = ctx1.find_create(num_params,den,itr1); + neg_assign((*itr1).second); + ctx2.find_create(num_params,den,itr2); + } else { + itr1 = ctx1.find_create(num_params,den); + neg_assign((*itr1).second); + ctx2.find_create(num_params,den); } } - neg_assign(ctx1[num_params], den); - ctx2[num_params] = den; // ctx2[0] += den-1; - ctx2[0] += den; - --ctx2[0]; + Coefficient& ctx2_0 = ctx2[0]; + ctx2_0 += den; + --ctx2_0; #ifdef NOISY_PIP { using namespace IO_Operators; Variables_Set::const_iterator p = parameters.begin(); - Linear_Expression expr1(ctx1[0]); - Linear_Expression expr2(ctx2[0]); + Linear_Expression expr1(ctx1.get(0)); + Linear_Expression expr2(ctx2_0); for (dimension_type j = 1; j <= num_params; ++j, ++p) { - expr1 += ctx1[j] * Variable(*p); - expr2 += ctx2[j] * Variable(*p); + expr1 += ctx1.get(j) * Variable(*p); + expr2 += ctx2.get(j) * Variable(*p); } std::cout << "Inserting into context: " << Constraint(expr1 >= 0) << " ; " @@ -3278,14 +3318,32 @@ PIP_Solution_Node::generate_cut(const dimension_type index, // Recompute references after possible reallocation. matrix_row_const_reference_type row_s = tableau.s[index]; matrix_row_const_reference_type row_t = tableau.t[index]; - for (dimension_type j = 0; j < num_vars; ++j) { - mod_assign(cut_s[j], row_s[j], den); - } - for (dimension_type j = 0; j < num_params; ++j) { - mod_assign(mod, row_t[j], den); - if (mod != 0) { - cut_t[j] = mod; - cut_t[j] -= den; + { + for (dimension_type j = 0; j < num_vars; ++j) { + mod_assign(cut_s[j], row_s[j], den); + } + } + { + matrix_const_row_const_iterator j = row_t.begin(); + matrix_const_row_const_iterator j_end = row_t.end(); + matrix_row_iterator cut_t_itr = cut_t.end(); + for ( ; j!=j_end; ++j) { + mod_assign(mod, (*j).second, den); + if (mod != 0) { + cut_t_itr = cut_t.find_create((*j).first,mod); + (*cut_t_itr).second -= den; + // Now cut_t_itr is valid, so we'll pass it in the next calls to + // find_create(). + ++j; + break; + } + } + for ( ; j!=j_end; ++j) { + mod_assign(mod, (*j).second, den); + if (mod != 0) { + cut_t_itr = cut_t.find_create((*j).first,mod,cut_t_itr); + (*cut_t_itr).second -= den; + } } } if (ap_column != not_a_dimension()) @@ -3300,12 +3358,12 @@ PIP_Solution_Node::generate_cut(const dimension_type index, dimension_type si = 0; for (dimension_type j = 0; j < space_dimension; ++j) { if (parameters.count(j) == 1) - expr += cut_t[ti++] * Variable(j); + expr += cut_t.get(ti++) * Variable(j); else - expr += cut_s[si++] * Variable(j); + expr += cut_s.get(si++) * Variable(j); } std::cout << "Adding cut: " - << Constraint(expr + cut_t[0] >= 0) + << Constraint(expr + cut_t.get(0) >= 0) << std::endl; } #endif

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: optimize solve() method for sparse matrices.
by Marco Poletti 14 Mar '10

14 Mar '10

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

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 14 Mar '10

14 Mar '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=965ed7268291… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:50:55 2010 +0100 PIP_Solution_Node: optimize solve() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e9bc08e3a715… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:39:34 2010 +0100 PIP_Solution_Node: prepare solve() method for optimizations. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e7478835f26c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:35:02 2010 +0100 PIP_Solution_Node: optimize solve() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7470baec3254… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:31:09 2010 +0100 Unlimited_Sparse_Row: fixed documentation of find_create(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9ca2459844e9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:30:41 2010 +0100 Sparse_Row, Sparse_Row_Reference: fixed documentation of find_create(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b13e2b9f9280… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:28:32 2010 +0100 Sparse_Row, Sparse_Row_Reference: add another versions of find_create(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=66a9aae45b80… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:27:50 2010 +0100 Dense_Row: added another version of find_create(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cab3898e8bc2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:09:23 2010 +0100 PIP_Tree_Node: add typedefs for matrix_row_copy_iterator and matrix_row_copy_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=165a8190a48d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:04:02 2010 +0100 PIP_Solution_Node: optimize solve() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b56d929ddf9a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 19:00:42 2010 +0100 Unlimited_Sparse_Row: add more find_create() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=748d84952206… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 18:32:40 2010 +0100 PIP_Solution_Node: prepare solve() method for optimizations. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e1fa1017d29f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 18:29:47 2010 +0100 PIP_Solution_Node: optimize solve() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=92f639ad2868… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 18:24:50 2010 +0100 PIP_Solution_Node::Tableau: optimize is_better_pivot() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fff0efe58756… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 18:13:09 2010 +0100 PIP_Solution_Node: optimize update_tableau() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e3a9ec053dc0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 18:12:29 2010 +0100 PIP_Tree.cc: fix compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4fad4c3e4b30… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 18:12:03 2010 +0100 PIP_Tree.cc: fix find_lexico_minimum_column_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6f650cb96107… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 17:17:39 2010 +0100 PIP_Tree_Node: optimize compatibility_check() for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=022902933ce5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 16:42:42 2010 +0100 PIP_Tree.cc: initial optimizations to compatibility_check(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=bf6273f8d28b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 16:20:29 2010 +0100 PIP_Tree.cc: little optimizations to find_lexico_minimum_column_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=383a2a37e899… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 16:13:39 2010 +0100 Dense_Row: weakened requirements of two-argument find() and lower_bound() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ef246da110a5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 15:40:45 2010 +0100 PIP_Tree.cc: optimize compatibility_check_find_pivot_in_set() for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e40c79b83368… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 15:25:31 2010 +0100 PIP_Tree.cc: little optimizations in compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d67331d400fb… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 15:16:14 2010 +0100 PIP_Tree.cc: cleaned up compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=036a07e0039f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 15:12:21 2010 +0100 PIP_Tree.cc: add assertions in compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dc4b05a2bc26… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 15:10:02 2010 +0100 PIP_Tree.cc: fix assertions in compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f804e4b85988… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 15:07:59 2010 +0100 PIP_Tree.cc: pass more data to compatibility_check_find_pivot_in_set() from compatibility_check_find_pivot(), greatly improving performance. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a5d084acc44a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 14:35:06 2010 +0100 PIP_Tree.cc: some optimizations to compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0a26f12190a5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 14:17:58 2010 +0100 PIP_Tree.cc: clean up compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=63c3a323f69f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 12:44:06 2010 +0100 PIP_Tree.cc: prepare compatibility_check_find_pivot_in_set() for optimization. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ec60cb34dc78… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 12:27:32 2010 +0100 PIP_Tree.cc: optimize compatibility_check_find_pivot() for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6de744c037c2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Mar 14 12:05:07 2010 +0100 PIP_Tree.cc: never pass the same column twice to compatibility_check_find_pivot_in_set() in function compatibility_check_find_pivot(), preparing for optimization.

1 0