Module: ppl/ppl Branch: master Commit: 5e070dcef88432381071a881976b65862b853396 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=5e070dcef8843...

Author: Roberto Bagnara bagnara@cs.unipr.it Date: Fri Sep 3 15:03:04 2010 +0200

Slight improvement to the selection mechanism for sparse and dense matrices.

---

src/MIP_Problem.cc | 26 +++++++++++++++++++------- src/MIP_Problem.defs.hh | 10 +++------- src/PIP_Problem.defs.hh | 9 +++------ src/PIP_Tree.cc | 22 +++++++++++----------- src/PIP_Tree.defs.hh | 16 ++++++++-------- src/globals.defs.hh | 5 +++++ 6 files changed, 49 insertions(+), 39 deletions(-)

diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 0a091ea..312f9e0 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -978,7 +978,8 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { // However, when using sparse matrices the first one is fast and the second // one is slow, and when using dense matrices the first one is slow and // the second one is fast. -#ifdef USE_PPL_SPARSE_MATRIX +#if USE_PPL_SPARSE_MATRIX + const dimension_type tableau_num_columns_minus_1 = tableau_num_columns - 1; // This is static to improve performance. // A pair (true, y) at position i means that @@ -989,7 +990,9 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { static std::vector<std::pair<bool, double> > columns; // The first element is not used. columns.resize(tableau_num_columns - 1); - for (dimension_type column = 1; column < tableau_num_columns_minus_1; ++column) + for (dimension_type column = 1; + column < tableau_num_columns_minus_1; + ++column) if (sgn(working_cost[column]) == cost_sign) { columns[column].first = true; columns[column].second = 1.0; @@ -1028,7 +1031,9 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { entering_index = i; } } -#else + +#else // !USE_PPL_SPARSE_MATRIX + double challenger_num = 0.0; double challenger_den = 0.0; for (dimension_type j = tableau_num_columns - 1; j-- > 1; ) { @@ -1063,7 +1068,9 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { WEIGHT_ADD_MUL(338, tableau_num_rows); } } -#endif + +#endif // !USE_PPL_SPARSE_MATRIX + return entering_index; }

@@ -1109,7 +1116,8 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { // However, when using sparse matrices the first one is fast and the second // one is slow, and when using dense matrices the first one is slow and // the second one is fast. -#ifdef USE_PPL_SPARSE_MATRIX +#if USE_PPL_SPARSE_MATRIX + const dimension_type tableau_num_columns = tableau.num_columns(); const dimension_type tableau_num_columns_minus_1 = tableau_num_columns - 1; // This is static to improve performance. @@ -1181,7 +1189,9 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { entering_index = k->first; } } -#else + +#else // !USE_PPL_SPARSE_MATRIX + PPL_DIRTY_TEMP_COEFFICIENT(challenger_den); for (dimension_type j = tableau.num_columns() - 1; j-- > 1; ) { const Coefficient& cost_j = working_cost[j]; @@ -1220,7 +1230,9 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { WEIGHT_ADD_MUL(47, tableau_num_rows); } } -#endif + +#endif // !USE_PPL_SPARSE_MATRIX + return entering_index; }

diff --git a/src/MIP_Problem.defs.hh b/src/MIP_Problem.defs.hh index 6f0aa86..607e139 100644 --- a/src/MIP_Problem.defs.hh +++ b/src/MIP_Problem.defs.hh @@ -25,12 +25,9 @@ site: http://www.cs.unipr.it/ppl/ . */

#include "MIP_Problem.types.hh" #include "globals.types.hh" - #include "Dense_Row.defs.hh" #include "Dense_Matrix.defs.hh" - #include "Sparse_Matrix.defs.hh" - #include "Linear_Expression.defs.hh" #include "Constraint.types.hh" #include "Constraint_System.types.hh" @@ -82,11 +79,10 @@ operator<<(std::ostream& s, const MIP_Problem& lp); */ class Parma_Polyhedra_Library::MIP_Problem { public: - -#ifndef USE_PPL_SPARSE_MATRIX - typedef Dense_Matrix matrix_type; -#else +#if USE_PPL_SPARSE_MATRIX typedef Sparse_Matrix matrix_type; +#else + typedef Dense_Matrix matrix_type; #endif

//! Builds a trivial MIP problem. diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 7eb26ec..646465d 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -40,10 +40,7 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "Dense_Row.defs.hh"

#include "Dense_Matrix.defs.hh" - #include "Sparse_Matrix.defs.hh" - - #include "Sparse_Row.defs.hh"

namespace Parma_Polyhedra_Library { @@ -497,10 +494,10 @@ operator<<(std::ostream& s, const PIP_Problem& p); */ class Parma_Polyhedra_Library::PIP_Problem { public: -#ifndef USE_PPL_SPARSE_MATRIX - typedef Dense_Matrix matrix_type; -#else +#if USE_PPL_SPARSE_MATRIX typedef Sparse_Matrix matrix_type; +#else + typedef Dense_Matrix matrix_type; #endif

//! Builds a trivial PIP problem. diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 091ede9..6a25531 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -152,29 +152,29 @@ merge_assign(PIP_Tree_Node::matrix_type& x, } }

-#ifndef USE_PPL_SPARSE_MATRIX +#if USE_PPL_SPARSE_MATRIX

+// Assigns to row x the negation of row y. inline void neg_assign_row(PIP_Tree_Node::matrix_type::row_type& x, const PIP_Tree_Node::matrix_type::row_type& y) { - for (dimension_type i = x.size(); i-- > 0; ) - neg_assign(x[i], y[i]); + x = y; + PIP_Tree_Node::matrix_type::row_type::iterator i = x.begin(); + PIP_Tree_Node::matrix_type::row_type::iterator i_end = x.end(); + for ( ; i != i_end; ++i) + neg_assign(i->second); }

-#else +#else // !USE_PPL_SPARSE_MATRIX

-// Assigns to row x the negation of row y. inline void neg_assign_row(PIP_Tree_Node::matrix_type::row_type& x, const PIP_Tree_Node::matrix_type::row_type& y) { - x = y; - PIP_Tree_Node::matrix_type::row_type::iterator i = x.begin(); - PIP_Tree_Node::matrix_type::row_type::iterator i_end = x.end(); - for ( ; i!=i_end; ++i) - neg_assign(i->second); + for (dimension_type i = x.size(); i-- > 0; ) + neg_assign(x[i], y[i]); }

-#endif // !defined(USE_PPL_SPARSE_MATRIX) +#endif // !USE_PPL_SPARSE_MATRIX

// Given context row \p y and denominator \p den, // to be interpreted as expression expr = y / den, diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 164d3b7..4ce1b75 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -33,15 +33,15 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "globals.defs.hh" #include "PIP_Problem.defs.hh"

-#ifndef USE_PPL_SPARSE_MATRIX +#if USE_PPL_SPARSE_MATRIX

-#include "Dense_Matrix.defs.hh" -#include "Dense_Row.defs.hh" +#include "Sparse_Matrix.defs.hh" +#include "Sparse_Row.defs.hh"

#else

-#include "Sparse_Matrix.defs.hh" -#include "Sparse_Row.defs.hh" +#include "Dense_Matrix.defs.hh" +#include "Dense_Row.defs.hh"

#endif

@@ -56,10 +56,10 @@ namespace Parma_Polyhedra_Library { */ class PIP_Tree_Node { public: -#ifndef USE_PPL_SPARSE_MATRIX - typedef Dense_Matrix matrix_type; -#else +#if USE_PPL_SPARSE_MATRIX typedef Sparse_Matrix matrix_type; +#else + typedef Dense_Matrix matrix_type; #endif

protected: diff --git a/src/globals.defs.hh b/src/globals.defs.hh index 62c1b95..ff5546c 100644 --- a/src/globals.defs.hh +++ b/src/globals.defs.hh @@ -469,6 +469,11 @@ FOK(mpq_class) #include "Weight_Profiler.defs.hh" #endif

+// By default, use dense matrices both for MIP_Problem and PIP_Problem. +#ifndef USE_PPL_SPARSE_MATRIX +#define USE_PPL_SPARSE_MATRIX 0 +#endif + #include "globals.inlines.hh"

#endif // !defined(PPL_globals_defs_hh)