Scippy

SoPlex

Sequential object-oriented simPlex

slufactor.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file slufactor.h
17  * @brief Implementation of Sparse Linear Solver.
18  */
19 #ifndef _SLUFACTOR_H_
20 #define _SLUFACTOR_H_
21 
22 #include <assert.h>
23 
24 #include "spxdefines.h"
25 #include "timerfactory.h"
26 #include "dvector.h"
27 #include "slinsolver.h"
28 #include "clufactor.h"
29 
30 namespace soplex
31 {
32 /// maximum nr. of factorization updates allowed before refactorization.
33 #define MAXUPDATES 1000
34 
35 /**@brief Implementation of Sparse Linear Solver.
36  * @ingroup Algo
37  *
38  * This class implements a #SLinSolver interface by using the sparse LU
39  * factorization implementet in #CLUFactor.
40  */
41 class SLUFactor : public SLinSolver, protected CLUFactor
42 {
43 public:
44 
45  //--------------------------------
46  /**@name Types */
47  //@{
48  /// Specifies how to perform \ref soplex::SLUFactor::change "change" method.
50  {
51  ETA = 0, ///<
53  };
54  /// for convenience
56  //@}
57 
58 private:
59 
60  //--------------------------------
61  /**@name Private data */
62  //@{
63  DVector vec; ///< Temporary vector
64  SSVector ssvec; ///< Temporary semi-sparse vector
65  //@}
66 
67 protected:
68 
69  //--------------------------------
70  /**@name Protected data */
71  //@{
72  bool usetup; ///< TRUE iff update vector has been setup
73  UpdateType uptype; ///< the current \ref soplex::SLUFactor::UpdateType "UpdateType".
74  SSVector eta; ///<
75  SSVector forest; ///< ? Update vector set up by solveRight4update() and solve2right4update()
76  Real lastThreshold; ///< pivoting threshold of last factorization
77  //@}
78 
79  //--------------------------------
80  /**@name Control Parameters */
81  //@{
82  /// minimum threshold to use.
84  /// minimum stability to achieve by setting threshold.
86  /// |x| < epsililon is considered to be 0.
88  /// Time spent in solves
91  /// Number of solves
93  //@}
94 
95 protected:
96 
97  //--------------------------------
98  /**@name Protected helpers */
99  //@{
100  ///
101  void freeAll();
102  ///
103  void changeEta(int idx, SSVector& eta);
104  //@}
105 
106 
107 public:
108 
109  //--------------------------------
110  /**@name Update type */
111  //@{
112  /// returns the current update type uptype.
114  {
115  return uptype;
116  }
117 
118  /// sets update type.
119  /** The new UpdateType becomes valid only after the next call to
120  method load().
121  */
123  {
124  uptype = tp;
125  }
126 
127  /// sets minimum Markowitz threshold.
129  {
130  if( m < 0.01 )
131  m = 0.01;
132 
133  if( m > 0.99 )
134  m = 0.99;
135 
136  minThreshold = m;
137  lastThreshold = m;
138  }
139 
140  /// returns Markowitz threshold.
142  {
143  return lastThreshold;
144  }
145  //@}
146 
147  //--------------------------------
148  /**@name Derived from SLinSolver
149  See documentation of \ref soplex::SLinSolver "SLinSolver" for a
150  documentation of these methods.
151  */
152  //@{
153  ///
154  void clear();
155  ///
156  int dim() const
157  {
158  return thedim;
159  }
160  ///
161  int memory() const
162  {
163  return nzCnt + l.start[l.firstUnused];
164  }
165  ///
166  const char* getName() const
167  {
168  return (uptype == SLUFactor::ETA) ? "SLU-Eta" : "SLU-Forest-Tomlin";
169  }
170  ///
171  Status status() const
172  {
173  return Status(stat);
174  }
175  ///
176  Real stability() const;
177  /// return condition number estimate based on the diagonal of U
178  Real conditionEstimate(int type = 0) const;
179  ///
180  std::string statistics() const;
181  ///
182  Status load(const SVector* vec[], int dim);
183  //@}
184 
185 public:
186 
187  //--------------------------------
188  /**@name Solve */
189  //@{
190  /// Solves \f$Ax=b\f$.
191  void solveRight (Vector& x, const Vector& b);
192  /// Solves \f$Ax=b\f$.
193  void solveRight (SSVector& x, const SVector& b);
194  /// Solves \f$Ax=b\f$.
195  void solveRight4update(SSVector& x, const SVector& b);
196  /// Solves \f$Ax=b\f$ and \f$Ay=d\f$.
197  void solve2right4update(SSVector& x, Vector& y, const SVector& b, SSVector& d);
198  /// Sparse version of solving two systems of equations
199  void solve2right4update(SSVector& x, SSVector& y, const SVector& b, SSVector& d);
200  /// Solves \f$Ax=b\f$, \f$Ay=d\f$ and \f$Az=e\f$.
201  void solve3right4update(SSVector& x, Vector& y, Vector& z,
202  const SVector& b, SSVector& d, SSVector& e);
203  /// sparse version of solving three systems of equations
205  const SVector& b, SSVector& d, SSVector& e);
206  /// sparse version of solving one system of equations with transposed basis matrix
207  void solveLeft(Vector& x, const Vector& b);
208  /// Solves \f$Ax=b\f$.
209  void solveLeft(SSVector& x, const SVector& b);
210  /// Solves \f$Ax=b\f$ and \f$Ay=d\f$.
211  void solveLeft(SSVector& x, Vector& y, const SVector& b, SSVector& d);
212  /// sparse version of solving two systems of equations with transposed basis matrix
213  void solveLeft(SSVector& x, SSVector& two, const SVector& b, SSVector& rhs2);
214  /// Solves \f$Ax=b\f$, \f$Ay=d\f$ and \f$Az=e\f$.
215  void solveLeft(SSVector& x, Vector& y, Vector& z,
216  const SVector& b, SSVector& d, SSVector& e);
217  /// sparse version of solving three systems of equations with transposed basis matrix
218  void solveLeft(SSVector& x, SSVector& y, SSVector& z,
219  const SVector& b, SSVector& d, SSVector& e);
220  ///
221  Status change(int idx, const SVector& subst, const SSVector* eta = 0);
222  //@}
223 
224  //--------------------------------
225  /**@name Miscellaneous */
226  //@{
227  /// time spent in factorizations
229  {
230  return factorTime->time();
231  }
232  /// reset FactorTime
234  {
235  factorTime->reset();
236  }
237  /// number of factorizations performed
238  int getFactorCount() const
239  {
240  return factorCount;
241  }
242  /// time spent in solves
244  {
245  return solveTime->time();
246  }
247  /// reset SolveTime
249  {
250  solveTime->reset();
251  }
252  /// number of solves performed
253  int getSolveCount() const
254  {
255  return solveCount;
256  }
257  /// reset timers and counters
259  {
260  factorTime->reset();
261  solveTime->reset();
262  factorCount = 0;
263  solveCount = 0;
264  }
265  /// prints the LU factorization to stdout.
266  void dump() const;
267 
268  /// consistency check.
269  bool isConsistent() const;
270  //@}
271 
272  //------------------------------------
273  /**@name Constructors / Destructors */
274  //@{
275  /// default constructor.
276  SLUFactor();
277  /// assignment operator.
278  SLUFactor& operator=(const SLUFactor& old);
279  /// copy constructor.
280  SLUFactor(const SLUFactor& old);
281  /// destructor.
282  virtual ~SLUFactor();
283  /// clone function for polymorphism
284  inline virtual SLinSolver* clone() const
285  {
286  return new SLUFactor(*this);
287  }
288  //@}
289 
290 private:
291 
292  //------------------------------------
293  /**@name Private helpers */
294  //@{
295  /// used to implement the assignment operator
296  void assign(const SLUFactor& old);
297  //@}
298 };
299 
300 } // namespace soplex
301 #endif // _SLUFACTOR_H_
void resetSolveTime()
reset SolveTime
Definition: slufactor.h:248
int getSolveCount() const
number of solves performed
Definition: slufactor.h:253
DVector vec
Temporary vector.
Definition: slufactor.h:63
UpdateType
Specifies how to perform change method.
Definition: slufactor.h:49
void solve2right4update(SSVector &x, Vector &y, const SVector &b, SSVector &d)
Solves and .
Definition: slufactor.cpp:106
Timer::TYPE timerType
Definition: slufactor.h:90
std::string statistics() const
Definition: slufactor.cpp:634
Status load(const SVector *vec[], int dim)
Definition: slufactor.cpp:1271
UpdateType uptype
the current UpdateType.
Definition: slufactor.h:73
void resetCounters()
reset timers and counters
Definition: slufactor.h:258
SSVector ssvec
Temporary semi-sparse vector.
Definition: slufactor.h:64
void solveLeft(Vector &x, const Vector &b)
sparse version of solving one system of equations with transposed basis matrix
Definition: slufactor.cpp:363
Real epsilon
|x| < epsililon is considered to be 0.
Definition: slufactor.h:87
void setUtype(UpdateType tp)
sets update type.
Definition: slufactor.h:122
const char * getName() const
Definition: slufactor.h:166
Real minStability
minimum stability to achieve by setting threshold.
Definition: slufactor.h:85
Real getFactorTime() const
time spent in factorizations
Definition: slufactor.h:228
virtual ~SLUFactor()
destructor.
Definition: slufactor.cpp:1245
void solveRight4update(SSVector &x, const SVector &b)
Solves .
Definition: slufactor.cpp:66
Real lastThreshold
pivoting threshold of last factorization
Definition: slufactor.h:76
int getFactorCount() const
number of factorizations performed
Definition: slufactor.h:238
L l
L matrix.
Definition: clufactor.h:198
virtual SLinSolver * clone() const
clone function for polymorphism
Definition: slufactor.h:284
Sparse Linear Solver virtual base class.
Timer * solveTime
Time spent in solves.
Definition: slufactor.h:89
Sparse Linear Solver virtual base class.Class SLinSolver provides a class for solving sparse linear s...
Definition: slinsolver.h:43
void solveRight(Vector &x, const Vector &b)
Solves .
Definition: slufactor.cpp:41
TimerFactory class.
Real minThreshold
minimum threshold to use.
Definition: slufactor.h:83
void changeEta(int idx, SSVector &eta)
Definition: slufactor.cpp:645
void resetFactorTime()
reset FactorTime
Definition: slufactor.h:233
Status status() const
Definition: slufactor.h:171
SLUFactor()
default constructor.
Definition: slufactor.cpp:1022
double Real
Definition: spxdefines.h:215
int solveCount
Number of solves.
Definition: slufactor.h:92
void setMarkowitz(Real m)
sets minimum Markowitz threshold.
Definition: slufactor.h:128
bool isConsistent() const
consistency check.
Definition: slufactor.cpp:1403
SLinSolver::Status stat
Status indicator.
Definition: clufactor.h:184
Dynamic vectors.
int factorCount
Number of factorizations.
Definition: clufactor.h:205
int firstUnused
number of first unused L vector
Definition: clufactor.h:164
Real conditionEstimate(int type=0) const
return condition number estimate based on the diagonal of U
Definition: slufactor.cpp:590
SLUFactor & operator=(const SLUFactor &old)
assignment operator.
Definition: slufactor.cpp:993
virtual Real time() const =0
int thedim
dimension of factorized matrix
Definition: clufactor.h:186
bool usetup
TRUE iff update vector has been setup.
Definition: slufactor.h:72
SSVector eta
Definition: slufactor.h:74
Real markowitz()
returns Markowitz threshold.
Definition: slufactor.h:141
Debugging, floating point type and parameter definitions.
Real stability() const
Definition: slufactor.cpp:578
Implementation of Sparse Linear Solver.This class implements a SLinSolver interface by using the spar...
Definition: slufactor.h:41
Implementation of sparse LU factorization.This class implements a sparse LU factorization with either...
Definition: clufactor.h:37
Everything should be within this namespace.
void assign(const SLUFactor &old)
used to implement the assignment operator
Definition: slufactor.cpp:796
TYPE
types of timers
Definition: timer.h:99
void solve3right4update(SSVector &x, Vector &y, Vector &z, const SVector &b, SSVector &d, SSVector &e)
Solves , and .
Definition: slufactor.cpp:223
Timer * factorTime
Time spent in factorizations.
Definition: clufactor.h:204
UpdateType utype() const
returns the current update type uptype.
Definition: slufactor.h:113
Implementation of sparse LU factorization.
int memory() const
Definition: slufactor.h:161
Real getSolveTime() const
time spent in solves
Definition: slufactor.h:243
void dump() const
prints the LU factorization to stdout.
Definition: slufactor.cpp:1412
int nzCnt
number of nonzeros in U
Definition: clufactor.h:187
int * start
starting positions in val and idx
Definition: clufactor.h:165
virtual void reset()=0
initialize timer, set timing accounts to zero.
Status
status flags of the SLinSolver class.
Definition: slinsolver.h:51
Status change(int idx, const SVector &subst, const SSVector *eta=0)
Definition: slufactor.cpp:654
int dim() const
Definition: slufactor.h:156
SSVector forest
? Update vector set up by solveRight4update() and solve2right4update()
Definition: slufactor.h:75
Wrapper for the system time query methods.
Definition: timer.h:76
SLinSolver::Status Status
for convenience
Definition: slufactor.h:55