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...

SLUFactor &	operator= (const SLUFactor &old)
	assignment operator. More...

	SLUFactor (const SLUFactor &old)
	copy constructor. More...

virtual	~SLUFactor ()
	destructor. More...

virtual SLinSolver *	clone () 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...

Timer *	solveTime
	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...

Real *	diag
	Array of pivot elements. More...

U	u
	U matrix. More...

Real *	work
	Working array: must always be left as 0! More...

Timer *	factorTime
	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
SPxOut *	spxout
	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

typedef SLinSolver::Status 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 ( )

default constructor.

Definition at line 1060 of file slufactor.cpp.

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

◆ SLUFactor() [2/2]

SLUFactor ( const SLUFactor & old )

copy constructor.

Definition at line 1196 of file slufactor.cpp.

References SLUFactor::assign(), CLUFactor::U::col, CLUFactor::col, TimerFactory::createTimer(), CLUFactor::diag, CLUFactor::U::Row::elem, CLUFactor::U::Col::elem, CLUFactor::factorTime, SLUFactor::freeAll(), CLUFactor::U::Row::idx, CLUFactor::U::Col::idx, CLUFactor::L::idx, SLUFactor::isConsistent(), CLUFactor::l, CLUFactor::U::Row::len, CLUFactor::U::Col::len, CLUFactor::U::Row::max, CLUFactor::U::Col::max, CLUFactor::Perm::orig, CLUFactor::Perm::perm, CLUFactor::L::rbeg, CLUFactor::L::ridx, CLUFactor::L::rorig, CLUFactor::U::row, CLUFactor::L::row, CLUFactor::row, CLUFactor::L::rperm, CLUFactor::L::rval, SLUFactor::solveCount, SLUFactor::solveTime, CLUFactor::U::Row::start, CLUFactor::U::Col::start, CLUFactor::L::start, SLUFactor::timerType, CLUFactor::u, CLUFactor::U::Row::val, CLUFactor::U::Col::val, and CLUFactor::L::val.

◆ ~SLUFactor()

~SLUFactor ( )

virtual

destructor.

Definition at line 1331 of file slufactor.cpp.

References CLUFactor::factorTime, SLUFactor::freeAll(), SLUFactor::solveTime, soplex::spx_free(), and Timer::~Timer().

Referenced by SLUFactor::resetCounters().

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.

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

◆ change()

SLUFactor::Status change	(	int	idx,
		const SVector &	subst,
		const SSVector *	eta = `0`
	)

virtual

◆ changeEta()

void changeEta	(	int	idx,
		SSVector &	eta
	)

protected

Definition at line 667 of file slufactor.cpp.

References SSVectorBase< R >::altIndexMem(), SSVectorBase< R >::altValues(), SSVectorBase< R >::forceSetup(), SSVectorBase< R >::setSize(), SSVectorBase< R >::size(), and CLUFactor::update().

Referenced by SLUFactor::change().

◆ clear()

void clear ( )

virtual

Implements SLinSolver.

Definition at line 740 of file slufactor.cpp.

References VectorBase< R >::clear(), SSVectorBase< R >::clear(), CLUFactor::U::col, CLUFactor::colMemMult, SLUFactor::epsilon, Param::epsilonFactorization(), SLUFactor::eta, CLUFactor::L::firstUnused, CLUFactor::L::firstUpdate, SLUFactor::forest, SLUFactor::freeAll(), CLUFactor::U::Row::idx, CLUFactor::U::Col::idx, CLUFactor::L::idx, CLUFactor::initMaxabs, CLUFactor::l, SLUFactor::lastThreshold, CLUFactor::lMemMult, CLUFactor::maxabs, MINSTABILITY, SLUFactor::minStability, SLUFactor::minThreshold, CLUFactor::L::rbeg, CLUFactor::L::ridx, CLUFactor::L::rorig, CLUFactor::U::row, CLUFactor::L::row, CLUFactor::rowMemMult, CLUFactor::L::rperm, CLUFactor::L::rval, CLUFactor::U::Row::size, CLUFactor::U::Col::size, CLUFactor::L::size, soplex::spx_alloc(), soplex::spx_free(), SLUFactor::ssvec, CLUFactor::L::start, CLUFactor::L::startSize, CLUFactor::stat, CLUFactor::thedim, CLUFactor::u, SLinSolver::UNLOADED, SLUFactor::usetup, CLUFactor::U::Row::val, CLUFactor::L::val, and SLUFactor::vec.

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

◆ 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()

void freeAll ( )

protected

◆ 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.