[PPL-devel] [GIT] ppl/ppl(master): Slight improvement to the selection mechanism for sparse and dense matrices .
Roberto Bagnara
bagnara at cs.unipr.it
Fri Sep 3 15:03:38 CEST 2010
Module: ppl/ppl
Branch: master
Commit: 5e070dcef88432381071a881976b65862b853396
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=5e070dcef88432381071a881976b65862b853396
Author: Roberto Bagnara <bagnara at 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)
More information about the PPL-devel
mailing list