Scippy

SoPlex

Sequential object-oriented simPlex

CLUFactorRational Class Reference

Implementation of sparse LU factorization with Rational precision.This class implements a sparse LU factorization with either FOREST-TOMLIN or ETA updates, using dynamic Markowitz pivoting. More...

#include <clufactor_rational.h>

Classes

struct  Dring
 
struct  L
 Data structures for saving the working matrix and L factor. More...
 
struct  Perm
 Data structures for saving the row and column permutations. More...
 
class  Pring
 Pivot Ring. More...
 
class  Temp
 Temporary data structures. More...
 
struct  U
 Data structures for saving the working matrix and U factor. More...
 

Protected Member Functions

Solver methods
void solveLright (Rational *vec)
 
int solveRight4update (Rational *vec, int *nonz, Rational *rhs, Rational *forest, int *forestNum, int *forestIdx)
 
void solveRight (Rational *vec, Rational *rhs)
 
int solveRight2update (Rational *vec1, Rational *vec2, Rational *rhs1, Rational *rhs2, int *nonz, Rational *forest, int *forestNum, int *forestIdx)
 
void solveRight2 (Rational *vec1, Rational *vec2, Rational *rhs1, Rational *rhs2)
 
void solveLeft (Rational *vec, Rational *rhs)
 
int solveLeftEps (Rational *vec, Rational *rhs, int *nonz)
 
int solveLeft2 (Rational *vec1, int *nonz, Rational *vec2, Rational *rhs1, Rational *rhs2)
 
int vSolveRight4update (Rational *vec, int *idx, Rational *rhs, int *ridx, int rn, Rational *forest, int *forestNum, int *forestIdx)
 
int vSolveRight4update2 (Rational *vec, int *idx, Rational *rhs, int *ridx, int rn, Rational *vec2, Rational *rhs2, int *ridx2, int rn2, Rational *forest, int *forestNum, int *forestIdx)
 
int vSolveRight4update3 (Rational *vec, int *idx, Rational *rhs, int *ridx, int rn, Rational *vec2, Rational *rhs2, int *ridx2, int rn2, Rational *vec3, Rational *rhs3, int *ridx3, int rn3, Rational *forest, int *forestNum, int *forestIdx)
 
void vSolveRightNoNZ (Rational *vec2, Rational *rhs2, int *ridx2, int rn2)
 
int vSolveLeft (Rational *vec, int *idx, Rational *rhs, int *ridx, int rn)
 
void vSolveLeftNoNZ (Rational *vec, Rational *rhs, int *ridx, int rn)
 
int vSolveLeft2 (Rational *vec, int *idx, Rational *rhs, int *ridx, int rn, Rational *vec2, Rational *rhs2, int *ridx2, int rn2)
 
int vSolveLeft3 (Rational *vec, int *idx, Rational *rhs, int *ridx, int rn, Rational *vec2, Rational *rhs2, int *ridx2, int rn2, Rational *vec3, Rational *rhs3, int *ridx3, int rn3)
 
void forestUpdate (int col, Rational *work, int num, int *nonz)
 Performs the Forrest-Tomlin update of the LU factorization. More...
 
void update (int p_col, Rational *p_work, const int *p_idx, int num)
 
void updateNoClear (int p_col, const Rational *p_work, const int *p_idx, int num)
 
void factor (const SVectorRational **vec, const Rational &threshold)
 pivoting threshold More...
 
Debugging
void dump () const
 
bool isConsistent () const
 

Protected Attributes

Protected data
SLinSolverRational::Status stat
 Status indicator. More...
 
int thedim
 dimension of factorized matrix More...
 
int nzCnt
 number of nonzeros in U More...
 
Rational initMaxabs
 maximum abs number in initail Matrix More...
 
Rational 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...
 
DVectorRational diag
 Array of pivot elements. More...
 
U u
 U matrix. More...
 
Rationalwork
 Working array: must always be left as 0! More...
 
TimerfactorTime
 Time spent in factorizations. More...
 
int factorCount
 Number of factorizations. More...
 
Real timeLimit
 Time limit on factorization or solves. More...
 

Private Member Functions

Solving

These helper methods are used during the factorization process. The solve*-methods solve lower and upper triangular systems from the left or from the right, respectively The methods with '2' in the end solve two systems at the same time. The methods with "Eps" in the end consider elements smaller then the passed epsilon as zero.

void solveUright (Rational *wrk, Rational *vec)
 
int solveUrightEps (Rational *vec, int *nonz, Rational *rhs)
 
void solveUright2 (Rational *work1, Rational *vec1, Rational *work2, Rational *vec2)
 
int solveUright2eps (Rational *work1, Rational *vec1, Rational *work2, Rational *vec2, int *nonz)
 
void solveLright2 (Rational *vec1, Rational *vec2)
 
void solveUpdateRight (Rational *vec)
 
void solveUpdateRight2 (Rational *vec1, Rational *vec2)
 
void solveUleft (Rational *work, Rational *vec)
 
void solveUleft2 (Rational *work1, Rational *vec1, Rational *work2, Rational *vec2)
 
int solveLleft2forest (Rational *vec1, int *, Rational *vec2)
 
void solveLleft2 (Rational *vec1, int *, Rational *vec2)
 
int solveLleftForest (Rational *vec, int *)
 
void solveLleft (Rational *vec)
 
int solveLleftEps (Rational *vec, int *nonz)
 
void solveUpdateLeft (Rational *vec)
 
void solveUpdateLeft2 (Rational *vec1, Rational *vec2)
 
int vSolveLright (Rational *vec, int *ridx, int rn)
 
void vSolveLright2 (Rational *vec, int *ridx, int *rnptr, Rational *vec2, int *ridx2, int *rn2ptr)
 
void vSolveLright3 (Rational *vec, int *ridx, int *rnptr, Rational *vec2, int *ridx2, int *rn2ptr, Rational *vec3, int *ridx3, int *rn3ptr)
 
int vSolveUright (Rational *vec, int *vidx, Rational *rhs, int *ridx, int rn)
 
void vSolveUrightNoNZ (Rational *vec, Rational *rhs, int *ridx, int rn)
 
int vSolveUright2 (Rational *vec, int *vidx, Rational *rhs, int *ridx, int rn, Rational *vec2, Rational *rhs2, int *ridx2, int rn2)
 
int vSolveUpdateRight (Rational *vec, int *ridx, int n)
 
void vSolveUpdateRightNoNZ (Rational *vec)
 
int solveUleft (Rational *vec, int *vecidx, Rational *rhs, int *rhsidx, int rhsn)
 
void solveUleftNoNZ (Rational *vec, Rational *rhs, int *rhsidx, int rhsn)
 
int solveLleftForest (Rational *vec, int *nonz, int n)
 
void solveLleftForestNoNZ (Rational *vec)
 
int solveLleft (Rational *vec, int *nonz, int rn)
 
void solveLleftNoNZ (Rational *vec)
 
int solveUpdateLeft (Rational *vec, int *nonz, int n)
 
void forestPackColumns ()
 
void forestMinColMem (int size)
 
void forestReMaxCol (int col, int len)
 
void initPerm ()
 
void initFactorMatrix (const SVectorRational **vec)
 
void minLMem (int size)
 
void setPivot (const int p_stage, const int p_col, const int p_row, const Rational &val)
 
void colSingletons ()
 
void rowSingletons ()
 
void initFactorRings ()
 
void freeFactorRings ()
 
int setupColVals ()
 
void setupRowVals ()
 
void eliminateRowSingletons ()
 
void eliminateColSingletons ()
 
void selectPivots (const Rational &threshold)
 
int updateRow (int r, int lv, int prow, int pcol, const Rational &pval)
 
void eliminatePivot (int prow, int pos)
 
void eliminateNucleus (const Rational &threshold)
 
void minRowMem (int size)
 
void minColMem (int size)
 
void remaxCol (int p_col, int len)
 
void packRows ()
 
void packColumns ()
 
void remaxRow (int p_row, int len)
 
int makeLvec (int p_len, int p_row)
 
bool timeLimitReached ()
 

Private Attributes

Private data
Temp temp
 Temporary storage. More...
 

Detailed Description

Implementation of sparse LU factorization with Rational precision.

This class implements a sparse LU factorization with either FOREST-TOMLIN or ETA updates, using dynamic Markowitz pivoting.

Definition at line 39 of file clufactor_rational.h.

Member Function Documentation

◆ colSingletons()

◆ dump()

◆ eliminateColSingletons()

◆ eliminateNucleus()

◆ eliminatePivot()

◆ eliminateRowSingletons()

◆ factor()

◆ forestMinColMem()

◆ forestPackColumns()

◆ forestReMaxCol()

◆ forestUpdate()

void forestUpdate ( int  p_col,
Rational p_work,
int  num,
int *  nonz 
)
protected

Performs the Forrest-Tomlin update of the LU factorization.

BH: I suppose this is implemented as described in UH Suhl, LM Suhl: A fast LU update for linear programming, Annals of OR 43, p. 33-47, 1993.

Parameters
p_colIndex of basis column to replace.
p_workDense vector to substitute in the basis.
numNumber of nonzeros in vector represented by p_work.
nonzIndices of nonzero elements in vector p_work.

The parameters num and nonz are used for the following optimization: If both are nonzero, indices of the nonzero elements provided in nonz (num giving their number) allow to access only those nonzero entries. Otherwise we have to go through the entire dense vector element by element.

After copying p_work into U, p_work is used to expand the row r, which is needed to restore the triangular structure of U.

Also num and nonz are used to maintain a heap if there are only very few nonzeros to be eliminated. This is plainly wrong if the method is called with nonz==0, see todo at the corresponding place below.

Exceptions
SPxStatusExceptionif the loaded matrix is singular
Todo:
Use an extra member variable as a buffer for working with the dense row instead of misusing p_work. I think that should be as efficient and much cleaner.

The following assert is obviously violated if this method is called with nonzero==0.

Todo:
Use an extra member variable as a buffer for the heap instead of misusing nonz and num. The method enQueueMin() seems to sort the nonzeros or something, for which it only needs some empty vector of size num.

Definition at line 692 of file clufactor_rational.cpp.

References CLUFactorRational::U::col, CLUFactorRational::col, soplex::deQueueMin(), CLUFactorRational::diag, soplex::enQueueMin(), CLUFactorRational::L::firstUnused, CLUFactorRational::forestReMaxCol(), CLUFactorRational::U::Row::idx, CLUFactorRational::U::Col::idx, CLUFactorRational::L::idx, CLUFactorRational::isConsistent(), CLUFactorRational::l, CLUFactorRational::U::Row::len, CLUFactorRational::U::Col::len, CLUFactorRational::makeLvec(), CLUFactorRational::U::Row::max, CLUFactorRational::U::Col::max, CLUFactorRational::maxabs, CLUFactorRational::nzCnt, SLinSolverRational::OK, CLUFactorRational::Perm::orig, CLUFactorRational::Perm::perm, CLUFactorRational::remaxRow(), CLUFactorRational::U::row, CLUFactorRational::row, SLinSolverRational::SINGULAR, soplex::spxAbs(), CLUFactorRational::U::Row::start, CLUFactorRational::U::Col::start, CLUFactorRational::L::start, CLUFactorRational::stat, CLUFactorRational::thedim, CLUFactorRational::u, CLUFactorRational::U::Col::used, CLUFactorRational::U::Row::val, CLUFactorRational::U::Col::val, and CLUFactorRational::L::val.

Referenced by SLUFactorRational::change(), and CLUFactorRational::timeLimitReached().

◆ freeFactorRings()

◆ initFactorMatrix()

◆ initFactorRings()

◆ initPerm()

◆ isConsistent()

◆ makeLvec()

◆ minColMem()

◆ minLMem()

◆ minRowMem()

◆ packColumns()

◆ packRows()

◆ remaxCol()

◆ remaxRow()

◆ rowSingletons()

◆ selectPivots()

◆ setPivot()

◆ setupColVals()

◆ setupRowVals()

void setupRowVals ( )
private

◆ solveLeft()

◆ solveLeft2()

◆ solveLeftEps()

◆ solveLleft() [1/2]

◆ solveLleft() [2/2]

◆ solveLleft2()

◆ solveLleft2forest()

◆ solveLleftEps()

◆ solveLleftForest() [1/2]

◆ solveLleftForest() [2/2]

◆ solveLleftForestNoNZ()

◆ solveLleftNoNZ()

◆ solveLright()

◆ solveLright2()

◆ solveRight()

◆ solveRight2()

◆ solveRight2update()

int solveRight2update ( Rational vec1,
Rational vec2,
Rational rhs1,
Rational rhs2,
int *  nonz,
Rational forest,
int *  forestNum,
int *  forestIdx 
)
protected

◆ solveRight4update()

◆ solveUleft() [1/2]

◆ solveUleft() [2/2]

◆ solveUleft2()

◆ solveUleftNoNZ()

◆ solveUpdateLeft() [1/2]

◆ solveUpdateLeft() [2/2]

◆ solveUpdateLeft2()

◆ solveUpdateRight()

◆ solveUpdateRight2()

◆ solveUright()

◆ solveUright2()

◆ solveUright2eps()

◆ solveUrightEps()

◆ timeLimitReached()

◆ update()

◆ updateNoClear()

◆ updateRow()

◆ vSolveLeft()

◆ vSolveLeft2()

◆ vSolveLeft3()

◆ vSolveLeftNoNZ()

◆ vSolveLright()

◆ vSolveLright2()

◆ vSolveLright3()

void vSolveLright3 ( Rational vec,
int *  ridx,
int *  rnptr,
Rational vec2,
int *  ridx2,
int *  rn2ptr,
Rational vec3,
int *  ridx3,
int *  rn3ptr 
)
private

◆ vSolveRight4update()

◆ vSolveRight4update2()

◆ vSolveRight4update3()

int vSolveRight4update3 ( Rational vec,
int *  idx,
Rational rhs,
int *  ridx,
int  rn,
Rational vec2,
Rational rhs2,
int *  ridx2,
int  rn2,
Rational vec3,
Rational rhs3,
int *  ridx3,
int  rn3,
Rational forest,
int *  forestNum,
int *  forestIdx 
)
protected

◆ vSolveRightNoNZ()

◆ vSolveUpdateRight()

◆ vSolveUpdateRightNoNZ()

◆ vSolveUright()

◆ vSolveUright2()

◆ vSolveUrightNoNZ()

Member Data Documentation

◆ col

◆ colMemMult

Real colMemMult
protected

◆ diag

◆ factorCount

◆ factorTime

◆ initMaxabs

Rational initMaxabs
protected

◆ l

L l
protected

L matrix.

Definition at line 199 of file clufactor_rational.h.

Referenced by SLUFactorRational::assign(), SLUFactorRational::change(), SLUFactorRational::clear(), CLUFactorRational::dump(), CLUFactorRational::eliminateRowSingletons(), CLUFactorRational::factor(), CLUFactorRational::forestUpdate(), SLUFactorRational::freeAll(), SLUFactorRational::load(), CLUFactorRational::makeLvec(), SLUFactorRational::memory(), CLUFactorRational::minLMem(), CLUFactorRational::rowSingletons(), CLUFactorRational::setupColVals(), SLUFactorRational::SLUFactorRational(), SLUFactorRational::solve2right4update(), SLUFactorRational::solve3right4update(), CLUFactorRational::solveLeft(), CLUFactorRational::solveLeft2(), CLUFactorRational::solveLeftEps(), CLUFactorRational::solveLleft(), CLUFactorRational::solveLleft2(), CLUFactorRational::solveLleft2forest(), CLUFactorRational::solveLleftEps(), CLUFactorRational::solveLleftForest(), CLUFactorRational::solveLleftForestNoNZ(), CLUFactorRational::solveLleftNoNZ(), CLUFactorRational::solveLright(), CLUFactorRational::solveLright2(), CLUFactorRational::solveRight(), CLUFactorRational::solveRight2(), CLUFactorRational::solveRight2update(), SLUFactorRational::solveRight4update(), CLUFactorRational::solveRight4update(), CLUFactorRational::solveUpdateLeft(), CLUFactorRational::solveUpdateLeft2(), CLUFactorRational::solveUpdateRight(), CLUFactorRational::solveUpdateRight2(), CLUFactorRational::update(), CLUFactorRational::updateNoClear(), CLUFactorRational::updateRow(), CLUFactorRational::vSolveLeft(), CLUFactorRational::vSolveLeft2(), CLUFactorRational::vSolveLeft3(), CLUFactorRational::vSolveLeftNoNZ(), CLUFactorRational::vSolveLright(), CLUFactorRational::vSolveLright2(), CLUFactorRational::vSolveLright3(), CLUFactorRational::vSolveRight4update(), CLUFactorRational::vSolveRight4update2(), CLUFactorRational::vSolveRight4update3(), CLUFactorRational::vSolveRightNoNZ(), CLUFactorRational::vSolveUpdateRight(), and CLUFactorRational::vSolveUpdateRightNoNZ().

◆ lMemMult

Real lMemMult
protected

factor of minimum Memory * number of nonzeros

Definition at line 194 of file clufactor_rational.h.

Referenced by SLUFactorRational::assign(), SLUFactorRational::clear(), and CLUFactorRational::initFactorMatrix().

◆ maxabs

◆ nzCnt

◆ row

◆ rowMemMult

Real rowMemMult
protected

factor of minimum Memory * number of nonzeros

Definition at line 192 of file clufactor_rational.h.

Referenced by SLUFactorRational::assign(), SLUFactorRational::clear(), CLUFactorRational::initFactorMatrix(), and CLUFactorRational::remaxRow().

◆ stat

◆ temp

◆ thedim

int thedim
protected

dimension of factorized matrix

Definition at line 187 of file clufactor_rational.h.

Referenced by SLUFactorRational::assign(), SLUFactorRational::clear(), CLUFactorRational::colSingletons(), SLUFactorRational::dim(), CLUFactorRational::dump(), CLUFactorRational::eliminateNucleus(), CLUFactorRational::factor(), CLUFactorRational::forestPackColumns(), CLUFactorRational::forestUpdate(), CLUFactorRational::initFactorMatrix(), CLUFactorRational::initFactorRings(), CLUFactorRational::initPerm(), CLUFactorRational::isConsistent(), SLUFactorRational::load(), CLUFactorRational::packColumns(), CLUFactorRational::packRows(), CLUFactorRational::rowSingletons(), CLUFactorRational::selectPivots(), CLUFactorRational::setupColVals(), SLUFactorRational::SLUFactorRational(), CLUFactorRational::solveLleft(), CLUFactorRational::solveLleft2(), CLUFactorRational::solveLleftEps(), CLUFactorRational::solveLleftForest(), CLUFactorRational::solveLleftForestNoNZ(), CLUFactorRational::solveLleftNoNZ(), CLUFactorRational::solveRight2update(), CLUFactorRational::solveRight4update(), CLUFactorRational::solveUleft(), CLUFactorRational::solveUleft2(), CLUFactorRational::solveUleftNoNZ(), CLUFactorRational::solveUpdateLeft(), CLUFactorRational::solveUright(), CLUFactorRational::solveUright2(), CLUFactorRational::solveUright2eps(), CLUFactorRational::solveUrightEps(), CLUFactorRational::vSolveLright(), CLUFactorRational::vSolveLright2(), CLUFactorRational::vSolveLright3(), CLUFactorRational::vSolveRight4update(), CLUFactorRational::vSolveRight4update2(), CLUFactorRational::vSolveRight4update3(), CLUFactorRational::vSolveRightNoNZ(), CLUFactorRational::vSolveUpdateRight(), CLUFactorRational::vSolveUpdateRightNoNZ(), CLUFactorRational::vSolveUright(), CLUFactorRational::vSolveUright2(), and CLUFactorRational::vSolveUrightNoNZ().

◆ timeLimit

Real timeLimit
protected

◆ u

◆ work