Scippy

SoPlex

Sequential object-oriented simPlex

CLUFactor< R > Class Template Reference

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

#include <clufactor.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...
 

Public Member Functions

void setTolerances (std::shared_ptr< Tolerances > tolerances)
 set tolerances More...
 
const std::shared_ptr< Tolerancestolerances () const
 get tolerances More...
 

Protected Member Functions

Solver methods
void solveLright (R *vec)
 
int solveRight4update (R *vec, int *nonz, R eps, R *rhs, R *forest, int *forestNum, int *forestIdx)
 
void solveRight (R *vec, R *rhs)
 
int solveRight2update (R *vec1, R *vec2, R *rhs1, R *rhs2, int *nonz, R eps, R *forest, int *forestNum, int *forestIdx)
 
void solveRight2 (R *vec1, R *vec2, R *rhs1, R *rhs2)
 
void solveLeft (R *vec, R *rhs)
 
int solveLeftEps (R *vec, R *rhs, int *nonz, R eps)
 
int solveLeft2 (R *vec1, int *nonz, R *vec2, R eps, R *rhs1, R *rhs2)
 
int vSolveRight4update (R eps, R *vec, int *idx, R *rhs, int *ridx, int rn, R *forest, int *forestNum, int *forestIdx)
 
int vSolveRight4update2 (R eps, R *vec, int *idx, R *rhs, int *ridx, int rn, R *vec2, R eps2, R *rhs2, int *ridx2, int rn2, R *forest, int *forestNum, int *forestIdx)
 
void vSolveRight4update2sparse (R eps, R *vec, int *idx, R *rhs, int *ridx, int &rn, R eps2, R *vec2, int *idx2, R *rhs2, int *ridx2, int &rn2, R *forest, int *forestNum, int *forestIdx)
 sparse version of above method More...
 
int vSolveRight4update3 (R eps, R *vec, int *idx, R *rhs, int *ridx, int rn, R *vec2, R eps2, R *rhs2, int *ridx2, int rn2, R *vec3, R eps3, R *rhs3, int *ridx3, int rn3, R *forest, int *forestNum, int *forestIdx)
 
void vSolveRight4update3sparse (R eps, R *vec, int *idx, R *rhs, int *ridx, int &rn, R eps2, R *vec2, int *idx2, R *rhs2, int *ridx2, int &rn2, R eps3, R *vec3, int *idx3, R *rhs3, int *ridx3, int &rn3, R *forest, int *forestNum, int *forestIdx)
 sparse version of above method More...
 
void vSolveRightNoNZ (R *vec, R eps, R *rhs, int *ridx, int rn)
 
int vSolveLeft (R eps, R *vec, int *idx, R *rhs, int *ridx, int rn)
 
void vSolveLeftNoNZ (R eps, R *vec, R *rhs, int *ridx, int rn)
 
int vSolveLeft2 (R eps, R *vec, int *idx, R *rhs, int *ridx, int rn, R *vec2, R *rhs2, int *ridx2, int rn2)
 
void vSolveLeft2sparse (R eps, R *vec, int *idx, R *rhs, int *ridx, int &rn, R *vec2, int *idx2, R *rhs2, int *ridx2, int &rn2)
 sparse version of solving 2 systems of equations More...
 
int vSolveLeft3 (R eps, R *vec, int *idx, R *rhs, int *ridx, int rn, R *vec2, R *rhs2, int *ridx2, int rn2, R *vec3, R *rhs3, int *ridx3, int rn3)
 
void vSolveLeft3sparse (R eps, R *vec, int *idx, R *rhs, int *ridx, int &rn, R *vec2, int *idx2, R *rhs2, int *ridx2, int &rn2, R *vec3, int *idx3, R *rhs3, int *ridx3, int &rn3)
 sparse version of solving 3 systems of equations More...
 
void forestUpdate (int col, R *work, int num, int *nonz)
 
void update (int p_col, R *p_work, const int *p_idx, int num)
 
void updateNoClear (int p_col, const R *p_work, const int *p_idx, int num)
 
void factor (const SVectorBase< R > **vec, R threshold, R eps)
 epsilon for zero detection More...
 
Debugging
void dump () const
 
bool isConsistent () const
 

Protected Attributes

Protected data
SLinSolver< R >::Status stat
 Status indicator. More...
 
int thedim
 dimension of factorized matrix More...
 
int nzCnt
 number of nonzeros in U More...
 
initMaxabs
 maximum abs number in initail Matrix More...
 
maxabs
 maximum abs number in L and U More...
 
rowMemMult
 factor of minimum Memory * number of nonzeros More...
 
colMemMult
 factor of minimum Memory * number of nonzeros More...
 
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...
 
std::vector< R > diag
 Array of pivot elements. More...
 
U u
 U matrix. More...
 
R * work
 Working array: must always be left as 0! More...
 
TimerfactorTime
 Time spent in factorizations. More...
 
int factorCount
 Number of factorizations. More...
 
int hugeValues
 number of times huge values occurred during solve (only used in debug mode) More...
 
std::shared_ptr< Tolerances_tolerances
 Tolerances for the factorization. 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 (R *wrk, R *vec) const
 
int solveUrightEps (R *vec, int *nonz, R eps, R *rhs)
 
void solveUright2 (R *work1, R *vec1, R *work2, R *vec2)
 
int solveUright2eps (R *work1, R *vec1, R *work2, R *vec2, int *nonz, R eps)
 
void solveLright2 (R *vec1, R *vec2)
 
void solveUpdateRight (R *vec)
 
void solveUpdateRight2 (R *vec1, R *vec2)
 
void solveUleft (R *work, R *vec)
 
void solveUleft2 (R *work1, R *vec1, R *work2, R *vec2)
 
int solveLleft2forest (R *vec1, int *, R *vec2, R)
 
void solveLleft2 (R *vec1, int *, R *vec2, R)
 
int solveLleftForest (R *vec, int *, R)
 
void solveLleft (R *vec) const
 
int solveLleftEps (R *vec, int *nonz, R eps)
 
void solveUpdateLeft (R *vec)
 
void solveUpdateLeft2 (R *vec1, R *vec2)
 
void updateSolutionVectorLright (R change, int j, R &vec, int *idx, int &nnz)
 
void vSolveLright (R *vec, int *ridx, int &rn, R eps)
 
void vSolveLright2 (R *vec, int *ridx, int &rn, R eps, R *vec2, int *ridx2, int &rn2, R eps2)
 
void vSolveLright3 (R *vec, int *ridx, int &rn, R eps, R *vec2, int *ridx2, int &rn2, R eps2, R *vec3, int *ridx3, int &rn3, R eps3)
 
int vSolveUright (R *vec, int *vidx, R *rhs, int *ridx, int rn, R eps)
 
void vSolveUrightNoNZ (R *vec, R *rhs, int *ridx, int rn, R eps)
 
int vSolveUright2 (R *vec, int *vidx, R *rhs, int *ridx, int rn, R eps, R *vec2, R *rhs2, int *ridx2, int rn2, R eps2)
 
int vSolveUpdateRight (R *vec, int *ridx, int n, R eps)
 
void vSolveUpdateRightNoNZ (R *vec, R)
 
int solveUleft (R eps, R *vec, int *vecidx, R *rhs, int *rhsidx, int rhsn)
 
void solveUleftNoNZ (R eps, R *vec, R *rhs, int *rhsidx, int rhsn)
 
int solveLleftForest (R eps, R *vec, int *nonz, int n)
 
void solveLleftForestNoNZ (R *vec)
 
int solveLleft (R eps, R *vec, int *nonz, int rn)
 
void solveLleftNoNZ (R *vec)
 
int solveUpdateLeft (R eps, R *vec, int *nonz, int n)
 
void forestPackColumns ()
 
void forestMinColMem (int size)
 
void forestReMaxCol (int col, int len)
 
void initPerm ()
 
void initFactorMatrix (const SVectorBase< R > **vec, const R eps)
 
void minLMem (int size)
 
void setPivot (const int p_stage, const int p_col, const int p_row, const R val)
 
void colSingletons ()
 
void rowSingletons ()
 
void initFactorRings ()
 
void freeFactorRings ()
 
int setupColVals ()
 
void setupRowVals ()
 
void eliminateRowSingletons ()
 
void eliminateColSingletons ()
 
void selectPivots (R threshold)
 
int updateRow (int r, int lv, int prow, int pcol, R pval, R eps)
 
void eliminatePivot (int prow, int pos, R eps)
 
void eliminateNucleus (const R eps, const R 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)
 

Private Attributes

Private data
Temp temp
 Temporary storage. More...
 

Detailed Description

template<class R>
class soplex::CLUFactor< R >

Implementation of sparse LU factorization.

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

Definition at line 49 of file clufactor.h.

Member Function Documentation

◆ colSingletons()

void colSingletons ( )
private

◆ dump()

void dump ( ) const
protected

◆ eliminateColSingletons()

void eliminateColSingletons ( )
private

◆ eliminateNucleus()

void eliminateNucleus ( const R  eps,
const R  threshold 
)
private

◆ eliminatePivot()

void eliminatePivot ( int  prow,
int  pos,
eps 
)
private

◆ eliminateRowSingletons()

void eliminateRowSingletons ( )
private

◆ factor()

void factor ( const SVectorBase< R > **  vec,
threshold,
eps 
)
protected

epsilon for zero detection

Parameters
vecArray of column VectorBase<R> pointers
thresholdpivoting threshold

◆ forestMinColMem()

void forestMinColMem ( int  size)
private

◆ forestPackColumns()

void forestPackColumns ( )
private

◆ forestReMaxCol()

void forestReMaxCol ( int  col,
int  len 
)
private

◆ forestUpdate()

void forestUpdate ( int  col,
R *  work,
int  num,
int *  nonz 
)
protected

◆ freeFactorRings()

void freeFactorRings ( )
private

◆ initFactorMatrix()

void initFactorMatrix ( const SVectorBase< R > **  vec,
const R  eps 
)
private

◆ initFactorRings()

void initFactorRings ( )
private

◆ initPerm()

void initPerm ( )
private

◆ isConsistent()

bool isConsistent ( ) const
protected

◆ makeLvec()

int makeLvec ( int  p_len,
int  p_row 
)
private

◆ minColMem()

void minColMem ( int  size)
private

◆ minLMem()

void minLMem ( int  size)
private

◆ minRowMem()

void minRowMem ( int  size)
private

◆ packColumns()

void packColumns ( )
private

◆ packRows()

void packRows ( )
private

◆ remaxCol()

void remaxCol ( int  p_col,
int  len 
)
private

◆ remaxRow()

void remaxRow ( int  p_row,
int  len 
)
private

◆ rowSingletons()

void rowSingletons ( )
private

◆ selectPivots()

void selectPivots ( threshold)
private

◆ setPivot()

void setPivot ( const int  p_stage,
const int  p_col,
const int  p_row,
const R  val 
)
private

◆ setTolerances()

void setTolerances ( std::shared_ptr< Tolerances tolerances)

set tolerances

Definition at line 54 of file clufactor.h.

◆ setupColVals()

int setupColVals ( )
private

◆ setupRowVals()

void setupRowVals ( )
private

◆ solveLeft()

void solveLeft ( R *  vec,
R *  rhs 
)
protected

◆ solveLeft2()

int solveLeft2 ( R *  vec1,
int *  nonz,
R *  vec2,
eps,
R *  rhs1,
R *  rhs2 
)
protected

◆ solveLeftEps()

int solveLeftEps ( R *  vec,
R *  rhs,
int *  nonz,
eps 
)
protected

◆ solveLleft() [1/2]

void solveLleft ( R *  vec) const
private

◆ solveLleft() [2/2]

int solveLleft ( eps,
R *  vec,
int *  nonz,
int  rn 
)
private

◆ solveLleft2()

void solveLleft2 ( R *  vec1,
int *  ,
R *  vec2,
 
)
private

◆ solveLleft2forest()

int solveLleft2forest ( R *  vec1,
int *  ,
R *  vec2,
 
)
private

◆ solveLleftEps()

int solveLleftEps ( R *  vec,
int *  nonz,
eps 
)
private

◆ solveLleftForest() [1/2]

int solveLleftForest ( R *  vec,
int *  ,
 
)
private

◆ solveLleftForest() [2/2]

int solveLleftForest ( eps,
R *  vec,
int *  nonz,
int  n 
)
private

◆ solveLleftForestNoNZ()

void solveLleftForestNoNZ ( R *  vec)
private

◆ solveLleftNoNZ()

void solveLleftNoNZ ( R *  vec)
private

◆ solveLright()

void solveLright ( R *  vec)
protected

◆ solveLright2()

void solveLright2 ( R *  vec1,
R *  vec2 
)
private

◆ solveRight()

void solveRight ( R *  vec,
R *  rhs 
)
protected

◆ solveRight2()

void solveRight2 ( R *  vec1,
R *  vec2,
R *  rhs1,
R *  rhs2 
)
protected

◆ solveRight2update()

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

◆ solveRight4update()

int solveRight4update ( R *  vec,
int *  nonz,
eps,
R *  rhs,
R *  forest,
int *  forestNum,
int *  forestIdx 
)
protected

◆ solveUleft() [1/2]

void solveUleft ( R *  work,
R *  vec 
)
private

◆ solveUleft() [2/2]

int solveUleft ( eps,
R *  vec,
int *  vecidx,
R *  rhs,
int *  rhsidx,
int  rhsn 
)
private

◆ solveUleft2()

void solveUleft2 ( R *  work1,
R *  vec1,
R *  work2,
R *  vec2 
)
private

◆ solveUleftNoNZ()

void solveUleftNoNZ ( eps,
R *  vec,
R *  rhs,
int *  rhsidx,
int  rhsn 
)
private

◆ solveUpdateLeft() [1/2]

void solveUpdateLeft ( R *  vec)
private

◆ solveUpdateLeft() [2/2]

int solveUpdateLeft ( eps,
R *  vec,
int *  nonz,
int  n 
)
private

◆ solveUpdateLeft2()

void solveUpdateLeft2 ( R *  vec1,
R *  vec2 
)
private

◆ solveUpdateRight()

void solveUpdateRight ( R *  vec)
private

◆ solveUpdateRight2()

void solveUpdateRight2 ( R *  vec1,
R *  vec2 
)
private

◆ solveUright()

void solveUright ( R *  wrk,
R *  vec 
) const
private

◆ solveUright2()

void solveUright2 ( R *  work1,
R *  vec1,
R *  work2,
R *  vec2 
)
private

◆ solveUright2eps()

int solveUright2eps ( R *  work1,
R *  vec1,
R *  work2,
R *  vec2,
int *  nonz,
eps 
)
private

◆ solveUrightEps()

int solveUrightEps ( R *  vec,
int *  nonz,
eps,
R *  rhs 
)
private

◆ tolerances()

const std::shared_ptr<Tolerances> tolerances ( ) const

get tolerances

Definition at line 59 of file clufactor.h.

Referenced by CLUFactor< BP >::setTolerances(), and SLUFactor< BP >::setTolerances().

◆ update()

void update ( int  p_col,
R *  p_work,
const int *  p_idx,
int  num 
)
protected

◆ updateNoClear()

void updateNoClear ( int  p_col,
const R *  p_work,
const int *  p_idx,
int  num 
)
protected

◆ updateRow()

int updateRow ( int  r,
int  lv,
int  prow,
int  pcol,
pval,
eps 
)
private

◆ updateSolutionVectorLright()

void updateSolutionVectorLright ( change,
int  j,
R &  vec,
int *  idx,
int &  nnz 
)
private

◆ vSolveLeft()

int vSolveLeft ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int  rn 
)
protected

◆ vSolveLeft2()

int vSolveLeft2 ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int  rn,
R *  vec2,
R *  rhs2,
int *  ridx2,
int  rn2 
)
protected

◆ vSolveLeft2sparse()

void vSolveLeft2sparse ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int &  rn,
R *  vec2,
int *  idx2,
R *  rhs2,
int *  ridx2,
int &  rn2 
)
protected

sparse version of solving 2 systems of equations

◆ vSolveLeft3()

int vSolveLeft3 ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int  rn,
R *  vec2,
R *  rhs2,
int *  ridx2,
int  rn2,
R *  vec3,
R *  rhs3,
int *  ridx3,
int  rn3 
)
protected

◆ vSolveLeft3sparse()

void vSolveLeft3sparse ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int &  rn,
R *  vec2,
int *  idx2,
R *  rhs2,
int *  ridx2,
int &  rn2,
R *  vec3,
int *  idx3,
R *  rhs3,
int *  ridx3,
int &  rn3 
)
protected

sparse version of solving 3 systems of equations

◆ vSolveLeftNoNZ()

void vSolveLeftNoNZ ( eps,
R *  vec,
R *  rhs,
int *  ridx,
int  rn 
)
protected

◆ vSolveLright()

void vSolveLright ( R *  vec,
int *  ridx,
int &  rn,
eps 
)
private

◆ vSolveLright2()

void vSolveLright2 ( R *  vec,
int *  ridx,
int &  rn,
eps,
R *  vec2,
int *  ridx2,
int &  rn2,
eps2 
)
private

◆ vSolveLright3()

void vSolveLright3 ( R *  vec,
int *  ridx,
int &  rn,
eps,
R *  vec2,
int *  ridx2,
int &  rn2,
eps2,
R *  vec3,
int *  ridx3,
int &  rn3,
eps3 
)
private

◆ vSolveRight4update()

int vSolveRight4update ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int  rn,
R *  forest,
int *  forestNum,
int *  forestIdx 
)
protected

◆ vSolveRight4update2()

int vSolveRight4update2 ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int  rn,
R *  vec2,
eps2,
R *  rhs2,
int *  ridx2,
int  rn2,
R *  forest,
int *  forestNum,
int *  forestIdx 
)
protected

◆ vSolveRight4update2sparse()

void vSolveRight4update2sparse ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int &  rn,
eps2,
R *  vec2,
int *  idx2,
R *  rhs2,
int *  ridx2,
int &  rn2,
R *  forest,
int *  forestNum,
int *  forestIdx 
)
protected

sparse version of above method

◆ vSolveRight4update3()

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

◆ vSolveRight4update3sparse()

void vSolveRight4update3sparse ( eps,
R *  vec,
int *  idx,
R *  rhs,
int *  ridx,
int &  rn,
eps2,
R *  vec2,
int *  idx2,
R *  rhs2,
int *  ridx2,
int &  rn2,
eps3,
R *  vec3,
int *  idx3,
R *  rhs3,
int *  ridx3,
int &  rn3,
R *  forest,
int *  forestNum,
int *  forestIdx 
)
protected

sparse version of above method

◆ vSolveRightNoNZ()

void vSolveRightNoNZ ( R *  vec,
eps,
R *  rhs,
int *  ridx,
int  rn 
)
protected

◆ vSolveUpdateRight()

int vSolveUpdateRight ( R *  vec,
int *  ridx,
int  n,
eps 
)
private

◆ vSolveUpdateRightNoNZ()

void vSolveUpdateRightNoNZ ( R *  vec,
 
)
private

◆ vSolveUright()

int vSolveUright ( R *  vec,
int *  vidx,
R *  rhs,
int *  ridx,
int  rn,
eps 
)
private

◆ vSolveUright2()

int vSolveUright2 ( R *  vec,
int *  vidx,
R *  rhs,
int *  ridx,
int  rn,
eps,
R *  vec2,
R *  rhs2,
int *  ridx2,
int  rn2,
eps2 
)
private

◆ vSolveUrightNoNZ()

void vSolveUrightNoNZ ( R *  vec,
R *  rhs,
int *  ridx,
int  rn,
eps 
)
private

Member Data Documentation

◆ _tolerances

std::shared_ptr<Tolerances> _tolerances
protected

Tolerances for the factorization.

Definition at line 230 of file clufactor.h.

Referenced by CLUFactor< BP >::setTolerances(), SLUFactor< BP >::setTolerances(), and CLUFactor< BP >::tolerances().

◆ col

Perm col
protected

column permutation matrices

Definition at line 219 of file clufactor.h.

◆ colMemMult

R colMemMult
protected

factor of minimum Memory * number of nonzeros

Definition at line 215 of file clufactor.h.

◆ diag

std::vector<R> diag
protected

Array of pivot elements.

Definition at line 222 of file clufactor.h.

◆ factorCount

int factorCount
protected

Number of factorizations.

Definition at line 228 of file clufactor.h.

Referenced by SLUFactor< BP >::getFactorCount(), and SLUFactor< BP >::resetCounters().

◆ factorTime

Timer* factorTime
protected

◆ hugeValues

int hugeValues
protected

number of times huge values occurred during solve (only used in debug mode)

Definition at line 229 of file clufactor.h.

Referenced by SLUFactor< BP >::resetCounters().

◆ initMaxabs

R initMaxabs
protected

maximum abs number in initail Matrix

Definition at line 211 of file clufactor.h.

◆ l

L l
protected

L matrix.

Definition at line 221 of file clufactor.h.

Referenced by SLUFactor< BP >::memory().

◆ lMemMult

R lMemMult
protected

factor of minimum Memory * number of nonzeros

Definition at line 216 of file clufactor.h.

◆ maxabs

R maxabs
protected

maximum abs number in L and U

Definition at line 212 of file clufactor.h.

◆ nzCnt

int nzCnt
protected

number of nonzeros in U

Definition at line 210 of file clufactor.h.

Referenced by SLUFactor< BP >::memory().

◆ row

Perm row
protected

row permutation matrices

Definition at line 218 of file clufactor.h.

◆ rowMemMult

R rowMemMult
protected

factor of minimum Memory * number of nonzeros

Definition at line 214 of file clufactor.h.

◆ stat

SLinSolver<R>::Status stat
protected

Status indicator.

Definition at line 207 of file clufactor.h.

Referenced by SLUFactor< BP >::status().

◆ temp

Temp temp
private

Temporary storage.

Definition at line 238 of file clufactor.h.

◆ thedim

int thedim
protected

dimension of factorized matrix

Definition at line 209 of file clufactor.h.

Referenced by SLUFactor< BP >::dim().

◆ u

U u
protected

U matrix.

Definition at line 223 of file clufactor.h.

◆ work

R* work
protected

Working array: must always be left as 0!

Definition at line 225 of file clufactor.h.