Scippy

SoPlex

Sequential object-oriented simPlex

SLUFactor Class Reference

Implementation of Sparse Linear Solver.This class implements a SLinSolver interface by using the sparse LU factorization implemented in CLUFactor. More...

#include <slufactor.h>

Public Types

Types
enum  UpdateType { ETA = 0, FOREST_TOMLIN }
 Specifies how to perform change method. More...
 
typedef SLinSolver::Status Status
 for convenience More...
 
- Public Types inherited from SLinSolver
enum  Status {
  OK = 0, INSTABLE = 1, SINGULAR = 2, UNLOADED = 4,
  ERROR = 8
}
 status flags of the SLinSolver class. More...
 

Public Member Functions

Update type
UpdateType utype () const
 returns the current update type uptype. More...
 
void setUtype (UpdateType tp)
 sets update type. More...
 
void setMarkowitz (Real m)
 sets minimum Markowitz threshold. More...
 
Real markowitz ()
 returns Markowitz threshold. More...
 
Derived from SLinSolver

See documentation of SLinSolver for a documentation of these methods.

void clear ()
 
int dim () const
 
int memory () const
 
const char * getName () const
 
Status status () const
 
Real stability () const
 
Real conditionEstimate (int type=0) const
 return condition number estimate based on the diagonal of U More...
 
std::string statistics () const
 
Status load (const SVector *vec[], int dim)
 
Solve
void solveRight (Vector &x, const Vector &b)
 Solves \(Ax=b\). More...
 
void solveRight (SSVector &x, const SSVector &b)
 
void solveRight (SSVector &x, const SVector &b)
 Solves \(Ax=b\). More...
 
void solveRight4update (SSVector &x, const SVector &b)
 Solves \(Ax=b\). More...
 
void solve2right4update (SSVector &x, Vector &y, const SVector &b, SSVector &d)
 Solves \(Ax=b\) and \(Ay=d\). More...
 
void solve2right4update (SSVector &x, SSVector &y, const SVector &b, SSVector &d)
 Sparse version of solving two systems of equations. More...
 
void solve3right4update (SSVector &x, Vector &y, Vector &z, const SVector &b, SSVector &d, SSVector &e)
 Solves \(Ax=b\), \(Ay=d\) and \(Az=e\). More...
 
void solve3right4update (SSVector &x, SSVector &y, SSVector &z, const SVector &b, SSVector &d, SSVector &e)
 sparse version of solving three systems of equations More...
 
void solveLeft (Vector &x, const Vector &b)
 sparse version of solving one system of equations with transposed basis matrix More...
 
void solveLeft (SSVector &x, const SSVector &b)
 
void solveLeft (SSVector &x, const SVector &b)
 Solves \(Ax=b\). More...
 
void solveLeft (SSVector &x, Vector &y, const SVector &b, SSVector &d)
 Solves \(Ax=b\) and \(Ay=d\). More...
 
void solveLeft (SSVector &x, SSVector &two, const SVector &b, SSVector &rhs2)
 sparse version of solving two systems of equations with transposed basis matrix More...
 
void solveLeft (SSVector &x, Vector &y, Vector &z, const SVector &b, SSVector &d, SSVector &e)
 Solves \(Ax=b\), \(Ay=d\) and \(Az=e\). More...
 
void solveLeft (SSVector &x, SSVector &y, SSVector &z, const SVector &b, SSVector &d, SSVector &e)
 sparse version of solving three systems of equations with transposed basis matrix More...
 
Status change (int idx, const SVector &subst, const SSVector *eta=0)
 
Miscellaneous
Real getFactorTime () const
 time spent in factorizations More...
 
void resetFactorTime ()
 reset FactorTime More...
 
int getFactorCount () const
 number of factorizations performed More...
 
Real getSolveTime () const
 time spent in solves More...
 
void resetSolveTime ()
 reset SolveTime More...
 
int getSolveCount () const
 number of solves performed More...
 
void resetCounters ()
 reset timers and counters More...
 
void dump () const
 prints the LU factorization to stdout. More...
 
bool isConsistent () const
 consistency check. More...
 
Constructors / Destructors
 SLUFactor ()
 default constructor. More...
 
SLUFactoroperator= (const SLUFactor &old)
 assignment operator. More...
 
 SLUFactor (const SLUFactor &old)
 copy constructor. More...
 
virtual ~SLUFactor ()
 destructor. More...
 
virtual SLinSolverclone () const
 clone function for polymorphism More...
 
- Public Member Functions inherited from SLinSolver
 SLinSolver ()
 default constructor More...
 
virtual ~SLinSolver ()
 destructor More...
 

Protected Member Functions

Protected helpers
void freeAll ()
 
void changeEta (int idx, SSVector &eta)
 
- Protected Member Functions inherited from CLUFactor
void solveLright (Real *vec)
 
int solveRight4update (Real *vec, int *nonz, Real eps, Real *rhs, Real *forest, int *forestNum, int *forestIdx)
 
void solveRight (Real *vec, Real *rhs)
 
int solveRight2update (Real *vec1, Real *vec2, Real *rhs1, Real *rhs2, int *nonz, Real eps, Real *forest, int *forestNum, int *forestIdx)
 
void solveRight2 (Real *vec1, Real *vec2, Real *rhs1, Real *rhs2)
 
void solveLeft (Real *vec, Real *rhs)
 
int solveLeftEps (Real *vec, Real *rhs, int *nonz, Real eps)
 
int solveLeft2 (Real *vec1, int *nonz, Real *vec2, Real eps, Real *rhs1, Real *rhs2)
 
int vSolveRight4update (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int rn, Real *forest, int *forestNum, int *forestIdx)
 
int vSolveRight4update2 (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int rn, Real *vec2, Real eps2, Real *rhs2, int *ridx2, int rn2, Real *forest, int *forestNum, int *forestIdx)
 
void vSolveRight4update2sparse (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int &rn, Real eps2, Real *vec2, int *idx2, Real *rhs2, int *ridx2, int &rn2, Real *forest, int *forestNum, int *forestIdx)
 sparse version of above method More...
 
int vSolveRight4update3 (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int rn, Real *vec2, Real eps2, Real *rhs2, int *ridx2, int rn2, Real *vec3, Real eps3, Real *rhs3, int *ridx3, int rn3, Real *forest, int *forestNum, int *forestIdx)
 
void vSolveRight4update3sparse (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int &rn, Real eps2, Real *vec2, int *idx2, Real *rhs2, int *ridx2, int &rn2, Real eps3, Real *vec3, int *idx3, Real *rhs3, int *ridx3, int &rn3, Real *forest, int *forestNum, int *forestIdx)
 sparse version of above method More...
 
void vSolveRightNoNZ (Real *vec, Real eps, Real *rhs, int *ridx, int rn)
 
int vSolveLeft (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int rn)
 
void vSolveLeftNoNZ (Real eps, Real *vec, Real *rhs, int *ridx, int rn)
 
int vSolveLeft2 (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int rn, Real *vec2, Real *rhs2, int *ridx2, int rn2)
 
void vSolveLeft2sparse (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int &rn, Real *vec2, int *idx2, Real *rhs2, int *ridx2, int &rn2)
 sparse version of solving 2 systems of equations More...
 
int vSolveLeft3 (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int rn, Real *vec2, Real *rhs2, int *ridx2, int rn2, Real *vec3, Real *rhs3, int *ridx3, int rn3)
 
void vSolveLeft3sparse (Real eps, Real *vec, int *idx, Real *rhs, int *ridx, int &rn, Real *vec2, int *idx2, Real *rhs2, int *ridx2, int &rn2, Real *vec3, int *idx3, Real *rhs3, int *ridx3, int &rn3)
 sparse version of solving 3 systems of equations More...
 
void forestUpdate (int col, Real *work, int num, int *nonz)
 Performs the Forrest-Tomlin update of the LU factorization. More...
 
void update (int p_col, Real *p_work, const int *p_idx, int num)
 
void updateNoClear (int p_col, const Real *p_work, const int *p_idx, int num)
 
void factor (const SVector **vec, Real threshold, Real eps)
 epsilon for zero detection More...
 
void dump () const
 
bool isConsistent () const
 

Protected Attributes

Protected data
bool usetup
 TRUE iff update vector has been setup. More...
 
UpdateType uptype
 the current UpdateType. More...
 
SSVector eta
 
SSVector forest
 ? Update vector set up by solveRight4update() and solve2right4update() More...
 
Real lastThreshold
 pivoting threshold of last factorization More...
 
Control Parameters
Real minThreshold
 minimum threshold to use. More...
 
Real minStability
 minimum stability to achieve by setting threshold. More...
 
Real epsilon
 |x| < epsililon is considered to be 0. More...
 
TimersolveTime
 Time spent in solves. More...
 
Timer::TYPE timerType
 
int solveCount
 Number of solves. More...
 
- Protected Attributes inherited from CLUFactor
SLinSolver::Status stat
 Status indicator. More...
 
int thedim
 dimension of factorized matrix More...
 
int nzCnt
 number of nonzeros in U More...
 
Real initMaxabs
 maximum abs number in initail Matrix More...
 
Real maxabs
 maximum abs number in L and U More...
 
Real rowMemMult
 factor of minimum Memory * number of nonzeros More...
 
Real colMemMult
 factor of minimum Memory * number of nonzeros More...
 
Real lMemMult
 factor of minimum Memory * number of nonzeros More...
 
Perm row
 row permutation matrices More...
 
Perm col
 column permutation matrices More...
 
L l
 L matrix. More...
 
Realdiag
 Array of pivot elements. More...
 
U u
 U matrix. More...
 
Realwork
 Working array: must always be left as 0! More...
 
TimerfactorTime
 Time spent in factorizations. More...
 
int factorCount
 Number of factorizations. More...
 

Private Member Functions

Private helpers
void assign (const SLUFactor &old)
 used to implement the assignment operator More...
 

Private Attributes

Private data
DVector vec
 Temporary vector. More...
 
SSVector ssvec
 Temporary semi-sparse vector. More...
 

Additional Inherited Members

- Public Attributes inherited from SLinSolver
SPxOutspxout
 message handler More...
 

Detailed Description

Implementation of Sparse Linear Solver.

This class implements a SLinSolver interface by using the sparse LU factorization implemented in CLUFactor.

Definition at line 41 of file slufactor.h.

Member Typedef Documentation

◆ Status

for convenience

Definition at line 55 of file slufactor.h.

Member Enumeration Documentation

◆ UpdateType

enum UpdateType

Specifies how to perform change method.

Enumerator
ETA 
FOREST_TOMLIN 

Definition at line 49 of file slufactor.h.

Constructor & Destructor Documentation

◆ SLUFactor() [1/2]

◆ SLUFactor() [2/2]

◆ ~SLUFactor()

~SLUFactor ( )
virtual

Member Function Documentation

◆ assign()

void assign ( const SLUFactor old)
private

used to implement the assignment operator

assignment used to implement operator=() and copy constructor. If this is initialised, freeAll() has to be called before. Class objects from SLUFactor are not copied here.

Definition at line 829 of file slufactor.cpp.

References CLUFactor::U::col, CLUFactor::col, CLUFactor::colMemMult, TimerFactory::createTimer(), CLUFactor::diag, CLUFactor::U::Row::elem, CLUFactor::U::Col::elem, SLUFactor::epsilon, CLUFactor::factorTime, CLUFactor::L::firstUnused, CLUFactor::L::firstUpdate, VectorBase< R >::get_ptr(), CLUFactor::Dring::idx, CLUFactor::U::Row::idx, CLUFactor::U::Col::idx, CLUFactor::L::idx, CLUFactor::initMaxabs, CLUFactor::l, SLUFactor::lastThreshold, CLUFactor::U::Row::len, CLUFactor::U::Col::len, CLUFactor::U::Row::list, CLUFactor::U::Col::list, CLUFactor::lMemMult, CLUFactor::U::Row::max, CLUFactor::U::Col::max, CLUFactor::maxabs, SLUFactor::minStability, SLUFactor::minThreshold, CLUFactor::Dring::next, CLUFactor::nzCnt, SLinSolver::OK, CLUFactor::Perm::orig, CLUFactor::Perm::perm, CLUFactor::Dring::prev, CLUFactor::L::rbeg, CLUFactor::L::ridx, CLUFactor::L::rorig, CLUFactor::U::row, CLUFactor::L::row, CLUFactor::row, CLUFactor::rowMemMult, CLUFactor::L::rperm, CLUFactor::L::rval, CLUFactor::U::Row::size, CLUFactor::U::Col::size, CLUFactor::L::size, SLUFactor::solveTime, soplex::spx_alloc(), SLinSolver::spxout, CLUFactor::U::Row::start, CLUFactor::U::Col::start, CLUFactor::L::start, CLUFactor::L::startSize, CLUFactor::stat, CLUFactor::thedim, Timer::type(), CLUFactor::u, CLUFactor::L::updateType, SLUFactor::uptype, CLUFactor::U::Row::used, CLUFactor::U::Col::used, CLUFactor::U::Row::val, CLUFactor::U::Col::val, CLUFactor::L::val, SLUFactor::vec, and CLUFactor::work.

Referenced by SLUFactor::clone(), SLUFactor::operator=(), and SLUFactor::SLUFactor().

◆ change()

◆ changeEta()

◆ clear()

◆ clone()

virtual SLinSolver* clone ( ) const
virtual

clone function for polymorphism

Implements SLinSolver.

Definition at line 295 of file slufactor.h.

References SLUFactor::assign(), and SLUFactor::SLUFactor().

◆ conditionEstimate()

Real conditionEstimate ( int  type = 0) const
virtual

return condition number estimate based on the diagonal of U

Implements SLinSolver.

Definition at line 602 of file slufactor.cpp.

References CLUFactor::diag, SLUFactor::dim(), and soplex::spxAbs().

Referenced by SLUFactor::status().

◆ dim()

int dim ( ) const
virtual

Implements SLinSolver.

Definition at line 157 of file slufactor.h.

References CLUFactor::thedim.

Referenced by SLUFactor::conditionEstimate(), SLUFactor::load(), and SLUFactor::status().

◆ dump()

void dump ( ) const

prints the LU factorization to stdout.

Definition at line 1502 of file slufactor.cpp.

References CLUFactor::dump().

Referenced by SLUFactor::load(), and SLUFactor::resetCounters().

◆ freeAll()

◆ getFactorCount()

int getFactorCount ( ) const
virtual

number of factorizations performed

Implements SLinSolver.

Definition at line 249 of file slufactor.h.

References CLUFactor::factorCount.

Referenced by SoPlex::_decompSimplifyAndSolve(), SoPlex::_solveRealLPAndRecordStatistics(), and SLUFactor::statistics().

◆ getFactorTime()

Real getFactorTime ( ) const

time spent in factorizations

Definition at line 239 of file slufactor.h.

References CLUFactor::factorTime, and Timer::time().

Referenced by SoPlex::_decompSimplifyAndSolve(), SoPlex::_solveRealLPAndRecordStatistics(), and SLUFactor::statistics().

◆ getName()

const char* getName ( ) const
virtual

Implements SLinSolver.

Definition at line 167 of file slufactor.h.

References SLUFactor::ETA.

◆ getSolveCount()

int getSolveCount ( ) const

number of solves performed

Definition at line 264 of file slufactor.h.

References SLUFactor::solveCount.

Referenced by SoPlex::_decompSimplifyAndSolve(), SoPlex::_solveRealLPAndRecordStatistics(), and SLUFactor::statistics().

◆ getSolveTime()

Real getSolveTime ( ) const

time spent in solves

Definition at line 254 of file slufactor.h.

References Timer::time().

Referenced by SoPlex::_decompSimplifyAndSolve(), SoPlex::_solveRealLPAndRecordStatistics(), and SLUFactor::statistics().

◆ isConsistent()

bool isConsistent ( ) const
virtual

consistency check.

Implements SLinSolver.

Definition at line 1493 of file slufactor.cpp.

References CLUFactor::isConsistent().

Referenced by SLUFactor::load(), SLUFactor::operator=(), SLUFactor::resetCounters(), and SLUFactor::SLUFactor().

◆ load()

SLUFactor::Status load ( const SVector vec[],
int  dim 
)
virtual
Todo:
if the factorization fails with stat = SINGULAR, distinuish between proven singularity (e.g., because of an empty column) and singularity due to numerics, that could be avoided by changing minStability and lastThreshold; in the first case, we want to abort, otherwise change the numerics

Implements SLinSolver.

Definition at line 1357 of file slufactor.cpp.

References soplex::betterThreshold(), SLUFactor::clear(), CLUFactor::U::col, CLUFactor::col, CLUFactor::diag, SLUFactor::dim(), SLUFactor::dump(), CLUFactor::U::Row::elem, CLUFactor::U::Col::elem, SLUFactor::epsilon, soplex::EQ(), SLUFactor::eta, CLUFactor::factor(), CLUFactor::L::firstUnused, CLUFactor::L::firstUpdate, SLUFactor::forest, VectorBase< R >::get_ptr(), CLUFactor::Dring::idx, initDR, SLUFactor::isConsistent(), CLUFactor::l, SLUFactor::lastThreshold, CLUFactor::U::Row::len, CLUFactor::U::Col::len, CLUFactor::U::Row::list, CLUFactor::U::Col::list, CLUFactor::U::Row::max, CLUFactor::U::Col::max, MAXUPDATES, MINSTABILITY, SLUFactor::minStability, SLUFactor::minThreshold, MSG_DEBUG, MSG_INFO3, SLinSolver::OK, CLUFactor::Perm::orig, CLUFactor::Perm::perm, DVectorBase< R >::reDim(), SSVectorBase< R >::reDim(), CLUFactor::U::row, CLUFactor::L::row, CLUFactor::row, SVectorBase< R >::size(), soplex::spx_realloc(), SLinSolver::spxout, SLUFactor::ssvec, SLUFactor::stability(), CLUFactor::U::Row::start, CLUFactor::U::Col::start, CLUFactor::L::start, CLUFactor::L::startSize, CLUFactor::stat, CLUFactor::thedim, CLUFactor::u, CLUFactor::L::updateType, SLUFactor::uptype, SLUFactor::usetup, SVectorBase< R >::value(), SLUFactor::vec, and CLUFactor::work.

Referenced by SLUFactor::status().

◆ markowitz()

Real markowitz ( )

returns Markowitz threshold.

Definition at line 142 of file slufactor.h.

References SLUFactor::clear(), and SLUFactor::lastThreshold.

Referenced by SoPlex::_solveRealStable().

◆ memory()

int memory ( ) const
virtual

Implements SLinSolver.

Definition at line 162 of file slufactor.h.

References CLUFactor::L::firstUnused, CLUFactor::l, CLUFactor::nzCnt, and CLUFactor::L::start.

◆ operator=()

◆ resetCounters()

◆ resetFactorTime()

void resetFactorTime ( )

reset FactorTime

Definition at line 244 of file slufactor.h.

References CLUFactor::factorTime, and Timer::reset().

◆ resetSolveTime()

void resetSolveTime ( )

reset SolveTime

Definition at line 259 of file slufactor.h.

References Timer::reset().

◆ setMarkowitz()

void setMarkowitz ( Real  m)

sets minimum Markowitz threshold.

Definition at line 129 of file slufactor.h.

Referenced by SoPlex::_solveRealStable().

◆ setUtype()

void setUtype ( UpdateType  tp)

sets update type.

The new UpdateType becomes valid only after the next call to method load().

Definition at line 123 of file slufactor.h.

Referenced by SoPlex::setIntParam().

◆ solve2right4update() [1/2]

◆ solve2right4update() [2/2]

◆ solve3right4update() [1/2]

◆ solve3right4update() [2/2]

◆ solveLeft() [1/7]

void solveLeft ( Vector x,
const Vector b 
)
virtual

sparse version of solving one system of equations with transposed basis matrix

Implements SLinSolver.

Definition at line 370 of file slufactor.cpp.

References VectorBase< R >::clear(), VectorBase< R >::get_ptr(), SLUFactor::solveCount, CLUFactor::solveLeft(), SLUFactor::solveTime, Timer::start(), Timer::stop(), and SLUFactor::vec.

Referenced by SLUFactor::solveLeft(), and SLUFactor::solveRight().

◆ solveLeft() [2/7]

void solveLeft ( SSVector x,
const SSVector b 
)
virtual

Implements SLinSolver.

Definition at line 214 of file slufactor.h.

References SLUFactor::change(), SLUFactor::solveLeft(), and SSVectorBase< R >::unSetup().

◆ solveLeft() [3/7]

◆ solveLeft() [4/7]

◆ solveLeft() [5/7]

◆ solveLeft() [6/7]

◆ solveLeft() [7/7]

◆ solveRight() [1/3]

void solveRight ( Vector x,
const Vector b 
)
virtual

◆ solveRight() [2/3]

◆ solveRight() [3/3]

◆ solveRight4update()

◆ stability()

Real stability ( ) const
virtual

◆ statistics()

std::string statistics ( ) const
virtual

◆ status()

◆ utype()

UpdateType utype ( ) const

returns the current update type uptype.

Definition at line 114 of file slufactor.h.

References SLUFactor::uptype.

Member Data Documentation

◆ epsilon

Real epsilon
protected

|x| < epsililon is considered to be 0.

Definition at line 88 of file slufactor.h.

Referenced by SLUFactor::assign(), SLUFactor::clear(), and SLUFactor::load().

◆ eta

◆ forest

◆ lastThreshold

Real lastThreshold
protected

pivoting threshold of last factorization

Definition at line 77 of file slufactor.h.

Referenced by SLUFactor::assign(), SLUFactor::clear(), SLUFactor::load(), and SLUFactor::markowitz().

◆ minStability

Real minStability
protected

minimum stability to achieve by setting threshold.

Definition at line 86 of file slufactor.h.

Referenced by SLUFactor::assign(), SLUFactor::clear(), and SLUFactor::load().

◆ minThreshold

Real minThreshold
protected

minimum threshold to use.

Definition at line 84 of file slufactor.h.

Referenced by SLUFactor::assign(), SLUFactor::clear(), and SLUFactor::load().

◆ solveCount

◆ solveTime

◆ ssvec

◆ timerType

Timer::TYPE timerType
protected

Definition at line 91 of file slufactor.h.

Referenced by SLUFactor::operator=(), and SLUFactor::SLUFactor().

◆ uptype

UpdateType uptype
protected

the current UpdateType.

Definition at line 73 of file slufactor.h.

Referenced by SLUFactor::assign(), SLUFactor::change(), SLUFactor::load(), and SLUFactor::utype().

◆ usetup

bool usetup
protected

◆ vec