SoPlex Documentation
Loading...
Searching...
No Matches
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-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file slufactor.h
26 * @brief Implementation of Sparse Linear Solver.
27 */
28#ifndef _SLUFACTOR_H_
29#define _SLUFACTOR_H_
30
31#include <assert.h>
32
33#include "soplex/spxdefines.h"
34#include "soplex/timerfactory.h"
35#include "soplex/slinsolver.h"
36#include "soplex/clufactor.h"
37
38namespace soplex
39{
40/// maximum nr. of factorization updates allowed before refactorization.
41#define MAXUPDATES 1000
42
43/**@brief Implementation of Sparse Linear Solver.
44 * @ingroup Algo
45 *
46 * This class implements a SLinSolver interface by using the sparse LU
47 * factorization implemented in CLUFactor.
48 */
49template <class R>
50class SLUFactor : public SLinSolver<R>, protected CLUFactor<R>
51{
52public:
53
54 //--------------------------------
55 /**@name Types */
56 ///@{
57 /// Specifies how to perform \ref soplex::SLUFactor<R>::change "change" method.
59 {
60 ETA = 0, ///<
61 FOREST_TOMLIN ///<
62 };
63 /// for convenience
64 using Status = typename SLinSolver<R>::Status;
65 ///@}
66
67private:
68
69 //--------------------------------
70 /**@name Private data */
71 ///@{
72 VectorBase<R> vec; ///< Temporary VectorBase<R>
73 SSVectorBase<R> ssvec; ///< Temporary semi-sparse VectorBase<R>
74 ///@}
75
76protected:
77
78 //--------------------------------
79 /**@name Protected data */
80 ///@{
81 bool usetup; ///< TRUE iff update vector has been setup
82 UpdateType uptype; ///< the current \ref soplex::SLUFactor<R>::UpdateType "UpdateType".
85 forest; ///< ? Update VectorBase<R> set up by solveRight4update() and solve2right4update()
86 R lastThreshold; ///< pivoting threshold of last factorization
87 ///@}
88
89 //--------------------------------
90 /**@name Control Parameters */
91 ///@{
92 /// minimum threshold to use.
94 /// minimum stability to achieve by setting threshold.
96 /// |x| < epsililon is considered to be 0.
98 /// Time spent in solves
101 /// Number of solves
103 ///@}
104
105protected:
106
107 //--------------------------------
108 /**@name Protected helpers */
109 ///@{
110 ///
111 void freeAll();
112 ///
114 ///@}
115
116
117public:
118
119 //--------------------------------
120 /**@name Update type */
121 ///@{
122 /// returns the current update type uptype.
124 {
125 return uptype;
126 }
127
128 /// sets update type.
129 /** The new UpdateType becomes valid only after the next call to
130 method load().
131 */
133 {
134 uptype = tp;
135 }
136
137 /// sets minimum Markowitz threshold.
139 {
140 if(m < 0.0001)
141 m = 0.0001;
142
143 if(m > 0.9999)
144 m = 0.9999;
145
146 minThreshold = m;
148 }
149
150 /// returns Markowitz threshold.
152 {
153 return lastThreshold;
154 }
155 ///@}
156
157 //--------------------------------
158 /**@name Derived from SLinSolver
159 See documentation of \ref soplex::SLinSolver "SLinSolver" for a
160 documentation of these methods.
161 */
162 ///@{
163 ///
164 void clear();
165 ///
166 int dim() const
167 {
168 return this->thedim;
169 }
170 ///
171 int memory() const
172 {
173 return this->nzCnt + this->l.start[this->l.firstUnused];
174 }
175 ///
176 const char* getName() const
177 {
178 return (uptype == SLUFactor<R>::ETA) ? "SLU-Eta" : "SLU-Forest-Tomlin";
179 }
180 ///
182 {
183 return Status(this->stat);
184 }
185 ///
186 R stability() const;
187 /** return one of several matrix metrics based on the diagonal of U
188 * 0: condition number estimate by ratio of min/max
189 * 1: trace (sum of diagonal elements)
190 * 2: determinant (product of diagonal elements)
191 */
192 R matrixMetric(int type = 0) const;
193 ///
194 std::string statistics() const;
195 ///
197 ///@}
198
199public:
200
201 //--------------------------------
202 /**@name Solve */
203 ///@{
204 /// Solves \f$Ax=b\f$.
207 {
208 x.unSetup();
210 }
211 /// Solves \f$Ax=b\f$.
213 /// Solves \f$Ax=b\f$.
215 /// Solves \f$Ax=b\f$ and \f$Ay=d\f$.
218 /// Sparse version of solving two systems of equations
221 /// Solves \f$Ax=b\f$, \f$Ay=d\f$ and \f$Az=e\f$.
224 /// sparse version of solving three systems of equations
227 /// sparse version of solving one system of equations with transposed basis matrix
230 {
231 x.unSetup();
233 }
234 /// Solves \f$Ax=b\f$.
236 /// Solves \f$Ax=b\f$ and \f$Ay=d\f$.
238 /// sparse version of solving two systems of equations with transposed basis matrix
241 /// Solves \f$Ax=b\f$, \f$Ay=d\f$ and \f$Az=e\f$.
244 /// sparse version of solving three systems of equations with transposed basis matrix
247 ///
248 Status change(int idx, const SVectorBase<R>& subst, const SSVectorBase<R>* eta = 0);
249 ///@}
250
251 //--------------------------------
252 /**@name Miscellaneous */
253 ///@{
254 /// time spent in factorizations
255 // @todo fix the return type from of the type form Real to a cpp time (Refactoring) TODO
257 {
258 return this->factorTime->time();
259 }
260 /// reset FactorTime
262 {
263 this->factorTime->reset();
264 }
265 /// number of factorizations performed
266 int getFactorCount() const
267 {
268 return this->factorCount;
269 }
270 /// time spent in solves
271 // @todo fix the return type of time to a cpp time type TODO
273 {
274 return solveTime->time();
275 }
276 /// reset SolveTime
278 {
279 solveTime->reset();
280 }
281 /// number of solves performed
282 int getSolveCount() const
283 {
284 return solveCount;
285 }
286 /// reset timers and counters
288 {
289 this->factorTime->reset();
290 solveTime->reset();
291 this->factorCount = 0;
292 this->hugeValues = 0;
293 solveCount = 0;
294 }
301 /// prints the LU factorization to stdout.
302 void dump() const;
303
304 /// consistency check.
305 bool isConsistent() const;
306 ///@}
307
308 //------------------------------------
309 /**@name Constructors / Destructors */
310 ///@{
311 /// default constructor.
312 SLUFactor<R>();
313 /// assignment operator.
315 /// copy constructor.
317 /// destructor.
318 virtual ~SLUFactor<R>();
319 /// clone function for polymorphism
320 inline virtual SLinSolver<R>* clone() const
321 {
322 return new SLUFactor<R>(*this);
323 }
324 ///@}
325
326private:
327
328 //------------------------------------
329 /**@name Private helpers */
330 ///@{
331 /// used to implement the assignment operator
332 void assign(const SLUFactor<R>& old);
333 ///@}
334};
335
336} // namespace soplex
337
338#include "slufactor.hpp"
339#endif // _SLUFACTOR_H_
Implementation of sparse LU factorization.
Definition clufactor.h:50
int factorCount
Number of factorizations.
Definition clufactor.h:217
Timer * factorTime
Time spent in factorizations.
Definition clufactor.h:216
int hugeValues
number of times huge values occurred during solve (only used in debug mode)
Definition clufactor.h:218
SLinSolver< R >::Status stat
Status indicator.
Definition clufactor.h:196
int thedim
dimension of factorized matrix
Definition clufactor.h:198
int nzCnt
number of nonzeros in U
Definition clufactor.h:199
Safe arrays of data objects.
Definition dataarray.h:75
Implementation of Sparse Linear Solver.
Definition slufactor.h:51
UpdateType
Specifies how to perform change method.
Definition slufactor.h:59
Timer * solveTime
Time spent in solves.
Definition slufactor.h:99
void changeEta(int idx, SSVectorBase< R > &eta)
void solveLeft(SSVectorBase< R > &x, SSVectorBase< R > &two, const SVectorBase< R > &b, SSVectorBase< R > &rhs2)
sparse version of solving two systems of equations with transposed basis matrix
R minStability
minimum stability to achieve by setting threshold.
Definition slufactor.h:95
Real getFactorTime() const
time spent in factorizations
Definition slufactor.h:256
bool isConsistent() const
consistency check.
void solve2right4update(SSVectorBase< R > &x, SSVectorBase< R > &y, const SVectorBase< R > &b, SSVectorBase< R > &d)
Sparse version of solving two systems of equations.
SLUFactor< R > & operator=(const SLUFactor< R > &old)
assignment operator.
void resetSolveTime()
reset SolveTime
Definition slufactor.h:277
void resetFactorTime()
reset FactorTime
Definition slufactor.h:261
UpdateType utype() const
returns the current update type uptype.
Definition slufactor.h:123
void solveLeft(SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &z, const SVectorBase< R > &b, SSVectorBase< R > &d, SSVectorBase< R > &e)
sparse version of solving three systems of equations with transposed basis matrix
SSVectorBase< R > forest
? Update VectorBase<R> set up by solveRight4update() and solve2right4update()
Definition slufactor.h:85
void setUtype(UpdateType tp)
sets update type.
Definition slufactor.h:132
void resetCounters()
reset timers and counters
Definition slufactor.h:287
UpdateType uptype
the current UpdateType.
Definition slufactor.h:82
void solveLeft(SSVectorBase< R > &x, const SSVectorBase< R > &b)
Definition slufactor.h:229
int solveCount
Number of solves.
Definition slufactor.h:102
Status change(int idx, const SVectorBase< R > &subst, const SSVectorBase< R > *eta=0)
const char * getName() const
Definition slufactor.h:176
void solveLeft(SSVectorBase< R > &x, const SVectorBase< R > &b)
Solves .
bool usetup
TRUE iff update vector has been setup.
Definition slufactor.h:81
R minThreshold
minimum threshold to use.
Definition slufactor.h:93
Timer::TYPE timerType
Definition slufactor.h:100
int memory() const
Definition slufactor.h:171
void solve2right4update(SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &b, SSVectorBase< R > &d)
Solves and .
virtual SLinSolver< R > * clone() const
clone function for polymorphism
Definition slufactor.h:320
void setMarkowitz(R m)
sets minimum Markowitz threshold.
Definition slufactor.h:138
void solveRight(SSVectorBase< R > &x, const SSVectorBase< R > &b)
Definition slufactor.h:206
void solveLeft(SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &z, const SVectorBase< R > &b, SSVectorBase< R > &d, SSVectorBase< R > &e)
Solves , and .
void assign(const SLUFactor< R > &old)
used to implement the assignment operator
void solveRight4update(SSVectorBase< R > &x, const SVectorBase< R > &b)
Solves .
SSVectorBase< R > eta
Definition slufactor.h:83
typename SLinSolver< R >::Status Status
for convenience
Definition slufactor.h:64
void solveRight(VectorBase< R > &x, const VectorBase< R > &b)
Solves .
int dim() const
Definition slufactor.h:166
SSVectorBase< R > ssvec
Temporary semi-sparse VectorBase<R>
Definition slufactor.h:73
int getSolveCount() const
number of solves performed
Definition slufactor.h:282
void solveLeft(VectorBase< R > &x, const VectorBase< R > &b)
sparse version of solving one system of equations with transposed basis matrix
int getFactorCount() const
number of factorizations performed
Definition slufactor.h:266
R lastThreshold
pivoting threshold of last factorization
Definition slufactor.h:86
void solveLeft(SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &b, SSVectorBase< R > &d)
Solves and .
std::string statistics() const
R stability() const
Status status() const
Definition slufactor.h:181
void changeTimer(const Timer::TYPE ttype)
Definition slufactor.h:295
void solve3right4update(SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &z, const SVectorBase< R > &b, SSVectorBase< R > &d, SSVectorBase< R > &e)
Solves , and .
void solve3right4update(SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &z, const SVectorBase< R > &b, SSVectorBase< R > &d, SSVectorBase< R > &e)
sparse version of solving three systems of equations
Real getSolveTime() const
time spent in solves
Definition slufactor.h:272
VectorBase< R > vec
Temporary VectorBase<R>
Definition slufactor.h:72
R matrixMetric(int type=0) const
R epsilon
|x| < epsililon is considered to be 0.
Definition slufactor.h:97
void dump() const
prints the LU factorization to stdout.
Status load(const SVectorBase< R > *vec[], int dim)
void solveRight(SSVectorBase< R > &x, const SVectorBase< R > &b)
Solves .
R markowitz()
returns Markowitz threshold.
Definition slufactor.h:151
Sparse Linear Solver virtual base class.
Definition slinsolver.h:53
Status
status flags of the SLinSolver class.
Definition slinsolver.h:61
static Timer * switchTimer(Timer *timer, Timer::TYPE ttype)
Wrapper for the system time query methods.
Definition timer.h:86
TYPE
types of timers
Definition timer.h:109
virtual void reset()=0
initialize timer, set timing accounts to zero.
virtual Real time() const =0
Implementation of sparse LU factorization.
Everything should be within this namespace.
Sparse Linear Solver virtual base class.
Debugging, floating point type and parameter definitions.
int * start
starting positions in val and idx
Definition clufactor.h:177
int firstUnused
number of first unused L vector
Definition clufactor.h:176
TimerFactory class.