Class SparseLU

java.lang.Object

org.ojalgo.matrix.decomposition.SparseLU

All Implemented Interfaces:

LDU<Double>, LU<Double>, MatrixDecomposition<Double>, MatrixDecomposition.Determinant<Double>, MatrixDecomposition.Ordered<Double>, MatrixDecomposition.Pivoting<Double>, MatrixDecomposition.RankRevealing<Double>, MatrixDecomposition.Solver<Double>, MatrixDecomposition.Updatable<Double>, Provider2D, Provider2D.Determinant<Double>, Provider2D.Inverse<Optional<MatrixStore<Double>>>, Provider2D.Rank, Provider2D.Solution<Optional<MatrixStore<Double>>>, DeterminantTask<Double>, InverterTask<Double>, MatrixTask<Double>, SolverTask<Double>, InvertibleFactor<Double>, Structure1D, Structure2D

public final class SparseLU
extends Object
implements LU<Double>

A sparse, primitive double based, LU decomposition with support for incremental Forrest-Tomlin updates.

Nested Class Summary

Nested classes/interfaces inherited from interface InvertibleFactor

InvertibleFactor.IdentityFactor<N>

Nested classes/interfaces inherited from interface LU

LU.Factory<N>

Nested classes/interfaces inherited from interface MatrixDecomposition

MatrixDecomposition.Determinant<N>, MatrixDecomposition.EconomySize<N>, MatrixDecomposition.Factor<N>, MatrixDecomposition.Factory<D>, MatrixDecomposition.Hermitian<N>, MatrixDecomposition.Ordered<N>, MatrixDecomposition.Pivoting<N>, MatrixDecomposition.RankRevealing<N>, MatrixDecomposition.Solver<N>, MatrixDecomposition.Updatable<N>, MatrixDecomposition.Values<N>

Nested classes/interfaces inherited from interface Provider2D

Provider2D.Condition, Provider2D.Determinant<N>, Provider2D.Eigenpairs, Provider2D.Hermitian, Provider2D.Inverse<M>, Provider2D.Rank, Provider2D.Solution<M>, Provider2D.Symmetric, Provider2D.Trace<N>

Nested classes/interfaces inherited from interface Structure1D

Structure1D.BasicMapper<T>, Structure1D.IndexMapper<T>, Structure1D.IntIndex, Structure1D.LongIndex, Structure1D.LoopCallback, Structure1D.Sparse

Nested classes/interfaces inherited from interface Structure2D

Structure2D.IntRowColumn, Structure2D.Logical<S,B>, Structure2D.LongRowColumn, Structure2D.ReducibleTo1D<R>, Structure2D.Reshapable, Structure2D.RowColumnKey<R,C>, Structure2D.RowColumnMapper<R,C>

Field Summary

Fields inherited from interface LU

C128, H256, Q128, R064, R128

Fields inherited from interface MatrixDecomposition

TYPICAL

Constructor Summary

Constructors

Constructor	Description
SparseLU()

Method Summary

Modifier and Type	Method	Description
void	btran(double[] arg)
void	btran(PhysicalStore<Double> arg)	Backwards-transformation
Double	calculateDeterminant(Access2D<?> matrix)
protected boolean	checkSolvability()
int	countEtaNonzeros()	Total nonzeros across all eta factors accumulated since the last factorisation.
int	countFactorNonzeros()	Total nonzeros in the L and U factors at the time of the last full factorisation (excluding the U diagonal which is always dense).
int	countSignificant(double threshold)
boolean	decompose(Access2D.Collectable<Double, ? super TransformableRegion<Double>> matrix)
boolean	factor(R064CSC matrix, int[] columns)	Factorises the basis formed by selecting columns from a CSC matrix.
void	ftran(double[] arg)
void	ftran(PhysicalStore<Double> arg)	Forward-transformation
int	getColDim()
Double	getDeterminant()	A matrix' determinant is the product of its eigenvalues.
double	getFactorMaxPivotMagnitude()	getMaxPivotMagnitude() as snapshotted at the moment of the last factorisation.
double	getFactorMinPivotMagnitude()	getMinPivotMagnitude() as snapshotted at the moment of the last factorisation.
List<InvertibleFactor<Double>>	getFactors()	[A]=[P][L][U][etas...]
MatrixStore<Double>	getInverse(PhysicalStore<Double> preallocated)	Implementing this method is optional.
MatrixStore<Double>	getL()
double	getMaxPivotMagnitude()	Largest pivot magnitude observed across the U diagonal — both the initial entries from factorisation and the new diagonals produced by FT updates since.
double	getMinPivotMagnitude()	Smallest pivot magnitude observed across the U diagonal — both the initial entries from factorisation and the new diagonals produced by FT updates since.
int[]	getPivotOrder()
double	getRankThreshold()
int[]	getReversePivotOrder()
int	getRowDim()
MatrixStore<Double>	getSolution(Access2D.Collectable<Double, ? super PhysicalStore<Double>> rhs, PhysicalStore<Double> preallocated)	Implementing this method is optional.
MatrixStore<Double>	getU()	If updateColumn(int, Access1D.Collectable) or invalid reference #updateColumn(int, Access1D.Collectable, PhysicalStore) has been invoked, then this is no longer guaranteed to be triangular.
MatrixStore<Double>	invert(Access2D<?> original, PhysicalStore<Double> preallocated)	Exactly how (if at all) a specific implementation makes use of preallocated is not specified by this interface.
final boolean	isComputed()
boolean	isPivoted()
boolean	isSolvable()	Please note that producing a pseudoinverse and/or a least squares solution is ok!
PhysicalStore<Double>	preallocate(int nbEquations, int nbVariables, int nbSolutions)
void	reset()	Delete computed results, and resets attributes to default values
MatrixStore<Double>	solve(Access2D<?> body, Access2D<?> rhs, PhysicalStore<Double> preallocated)	Exactly how (if at all) a specific implementation makes use of preallocated is not specified by this interface.
boolean	updateColumn(int specifiedColumn, R064CSC matrix, int sourceColumn)	Forrest-Tomlin update reading the new column directly from a CSC matrix.
boolean	updateColumn(int specifiedColumn, Access1D.Collectable<Double, ? super TransformableRegion<Double>> newColumn)	The Forrest-Tomlin update algorithm

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface InverterTask

invert, preallocate

Methods inherited from interface LDU

isOrdered

Methods inherited from interface LU

getSolution, reconstruct

Methods inherited from interface MatrixDecomposition

isComputed, reset

Methods inherited from interface MatrixDecomposition.Determinant

toDeterminantProvider

Methods inherited from interface MatrixDecomposition.Pivoting

decomposeWithoutPivoting

Methods inherited from interface MatrixDecomposition.RankRevealing

getRank, isFullRank

Methods inherited from interface MatrixDecomposition.Solver

compute, getInverse, invert, preallocate, solve, toInverseProvider, toSolutionProvider

Methods inherited from interface SolverTask

preallocate, solve

Methods inherited from interface Structure2D

count, countColumns, countRows, firstInColumn, firstInRow, getMaxDim, getMinDim, isEmpty, isFat, isScalar, isSquare, isTall, isVector, limitOfColumn, limitOfRow, size

Constructor Details

SparseLU

public SparseLU()

Method Details

btran

public void btran(double[] arg)

Specified by:

btran in interface InvertibleFactor<Double>

See Also:

• InvertibleFactor.IdentityFactor.btran(PhysicalStore)

btran

public void btran(PhysicalStore<Double> arg)

Description copied from interface: InvertibleFactor

Backwards-transformation

Solve [x]^T[A] = [b]^T (equivalent to [A]^T[x] = [b]) by transforming [b] into [x] in-place.

Specified by:

btran in interface InvertibleFactor<Double>

Parameters:

arg - [b] transformed into [x]

calculateDeterminant

public Double calculateDeterminant(Access2D<?> matrix)

Specified by:

calculateDeterminant in interface DeterminantTask<Double>

countEtaNonzeros

public int countEtaNonzeros()

Total nonzeros across all eta factors accumulated since the last factorisation. Each eta factor corresponds to one Forrest-Tomlin update (column replacement in the basis).

countFactorNonzeros

public int countFactorNonzeros()

Total nonzeros in the L and U factors at the time of the last full factorisation (excluding the U diagonal which is always dense). Returns 0 before the first factorisation.

getMaxPivotMagnitude

public double getMaxPivotMagnitude()

Largest pivot magnitude observed across the U diagonal — both the initial entries from factorisation and the new diagonals produced by FT updates since.

getMinPivotMagnitude

public double getMinPivotMagnitude()

Smallest pivot magnitude observed across the U diagonal — both the initial entries from factorisation and the new diagonals produced by FT updates since.

getFactorMaxPivotMagnitude

public double getFactorMaxPivotMagnitude()

getMaxPivotMagnitude() as snapshotted at the moment of the last factorisation. Captures the basis-only diagonal range, before any FT updates contributed.

getFactorMinPivotMagnitude

public double getFactorMinPivotMagnitude()

getMinPivotMagnitude() as snapshotted at the moment of the last factorisation. Captures the basis-only diagonal range, before any FT updates contributed.

countSignificant

public int countSignificant(double threshold)

Specified by:

countSignificant in interface MatrixDecomposition.RankRevealing<Double>

Parameters:

threshold - Significance limit

Returns:

The number of elements in the diagonal matrix that are greater than the threshold

decompose

public boolean decompose(Access2D.Collectable<Double, ? super TransformableRegion<Double>> matrix)

Specified by:

decompose in interface MatrixDecomposition<Double>

Parameters:

matrix - A matrix to decompose

Returns:

true if decomposition suceeded; false if not

factor

public boolean factor(R064CSC matrix,
 int[] columns)

Factorises the basis formed by selecting columns from a CSC matrix. This is the primary entry point for the revised simplex solver.

Parameters:

matrix - The full constraint matrix in CSC format

columns - The indices of the columns that form the basis

ftran

public void ftran(double[] arg)

Specified by:

ftran in interface InvertibleFactor<Double>

See Also:

• InvertibleFactor.IdentityFactor.ftran(PhysicalStore)

ftran

public void ftran(PhysicalStore<Double> arg)

Description copied from interface: InvertibleFactor

Forward-transformation

Solve [A][x] = [b] by transforming [b] into [x] in-place.

Specified by:

ftran in interface InvertibleFactor<Double>

Parameters:

arg - [b] transformed into [x]

getColDim

public int getColDim()

Specified by:

getColDim in interface Structure2D

Returns:

The number of columns

getDeterminant

public Double getDeterminant()

Description copied from interface: MatrixDecomposition.Determinant

A matrix' determinant is the product of its eigenvalues.

Specified by:

getDeterminant in interface MatrixDecomposition.Determinant<Double>

Specified by:

getDeterminant in interface Provider2D.Determinant<Double>

Returns:

The matrix' determinant

getFactors

public List<InvertibleFactor<Double>> getFactors()

[A]=[P][L][U][etas...][Q]

Specified by:

getFactors in interface MatrixDecomposition.Solver<Double>

getInverse

public MatrixStore<Double> getInverse(PhysicalStore<Double> preallocated)

Description copied from interface: MatrixDecomposition.Solver

Implementing this method is optional.

Exactly how a specific implementation makes use of preallocated is not specified by this interface. It must be documented for each implementation.

Should produce the same results as calling MatrixDecomposition.Solver.getInverse().

Specified by:

getInverse in interface MatrixDecomposition.Solver<Double>

Parameters:

preallocated - Preallocated memory for the results, possibly some intermediate results. You must assume this is modified, but you cannot assume it will contain the full/final/correct solution. Use MatrixDecomposition.Solver.preallocate(int, int) or InverterTask.preallocate(Structure2D) to get a suitable instance.

Returns:

The inverse, this is where you get the solution

getL

public MatrixStore<Double> getL()

Specified by:

getL in interface LU<Double>

getPivotOrder

public int[] getPivotOrder()

Specified by:

getPivotOrder in interface MatrixDecomposition.Pivoting<Double>

Returns:

The pivot (row and/or columnn) order

getRankThreshold

public double getRankThreshold()

Specified by:

getRankThreshold in interface MatrixDecomposition.RankRevealing<Double>

getReversePivotOrder

public int[] getReversePivotOrder()

Specified by:

getReversePivotOrder in interface MatrixDecomposition.Pivoting<Double>

getRowDim

public int getRowDim()

Specified by:

getRowDim in interface Structure2D

Returns:

The number of rows

getSolution

public MatrixStore<Double> getSolution(Access2D.Collectable<Double, ? super PhysicalStore<Double>> rhs,
 PhysicalStore<Double> preallocated)

Description copied from interface: MatrixDecomposition.Solver

Implementing this method is optional.

Exactly how a specific implementation makes use of preallocated is not specified by this interface. It must be documented for each implementation.

Should produce the same results as calling MatrixDecomposition.Solver.getSolution(Collectable).

Specified by:

getSolution in interface MatrixDecomposition.Solver<Double>

Parameters:

rhs - The Right Hand Side, wont be modfied

preallocated - Preallocated memory for the results, possibly some intermediate results. You must assume this is modified, but you cannot assume it will contain the full/final/correct solution. Use SolverTask.preallocate(int, int, int) or SolverTask.preallocate(Structure2D, Structure2D) to get a suitable instance.

Returns:

The solution

getU

public MatrixStore<Double> getU()

If updateColumn(int, Access1D.Collectable) or

invalid reference

#updateColumn(int, Access1D.Collectable, PhysicalStore)

has been invoked, then this is no longer guaranteed to be triangular.

Specified by:

getU in interface LU<Double>

See Also:

• MatrixDecomposition.Pivoting.getPivotOrder()
• LU.getL()

invert

public MatrixStore<Double> invert(Access2D<?> original,
 PhysicalStore<Double> preallocated)
                           throws RecoverableCondition

Description copied from interface: InverterTask

Exactly how (if at all) a specific implementation makes use of preallocated is not specified by this interface. It must be documented for each implementation.

Should produce the same results as calling InverterTask.invert(Access2D).

Use InverterTask.preallocate(Structure2D) to obtain a suitbale preallocated.

Specified by:

invert in interface InverterTask<Double>

Parameters:

preallocated - Preallocated memory for the results, possibly some intermediate results. You must assume this is modified, but you cannot assume it will contain the full/final/correct solution.

Returns:

The inverse

Throws:

RecoverableCondition - TODO

isPivoted

public boolean isPivoted()

Specified by:

isPivoted in interface MatrixDecomposition.Pivoting<Double>

Returns:

true if any pivoting was actually done

isSolvable

public boolean isSolvable()

Description copied from interface: MatrixDecomposition.Solver

Please note that producing a pseudoinverse and/or a least squares solution is ok! The return value, of this method, is not an indication of if the decomposed matrix is square, has full rank, is postive definite or whatever. It's that in combination with the specific decomposition algorithm's capabilities.

Specified by:

isSolvable in interface MatrixDecomposition.Solver<Double>

Returns:

true if this matrix decomposition is in a state to be able to deliver an inverse or an equation system solution (with some degree of numerical stability).

preallocate

public PhysicalStore<Double> preallocate(int nbEquations,
 int nbVariables,
 int nbSolutions)

Specified by:

preallocate in interface SolverTask<Double>

solve

public MatrixStore<Double> solve(Access2D<?> body,
 Access2D<?> rhs,
 PhysicalStore<Double> preallocated)
                          throws RecoverableCondition

Description copied from interface: SolverTask

Exactly how (if at all) a specific implementation makes use of preallocated is not specified by this interface. It must be documented for each implementation.

Should produce the same results as calling SolverTask.solve(Access2D, Access2D).

Use SolverTask.preallocate(Structure2D, Structure2D) to obtain a suitbale preallocated.

Specified by:

solve in interface SolverTask<Double>

Parameters:

rhs - The Right Hand Side, wont be modfied

preallocated - Preallocated memory for the results, possibly some intermediate results. You must assume this is modified, but you cannot assume it will contain the full/ /correct solution.

Returns:

The solution

Throws:

RecoverableCondition

updateColumn

public boolean updateColumn(int specifiedColumn,
 Access1D.Collectable<Double, ? super TransformableRegion<Double>> newColumn)

The Forrest-Tomlin update algorithm

Specified by:

updateColumn in interface MatrixDecomposition.Updatable<Double>

Parameters:

specifiedColumn - The index of the column, in the original matrix, to replace

newColumn - The new column values

Returns:

true if update was successful, false if not.

updateColumn

public boolean updateColumn(int specifiedColumn,
 R064CSC matrix,
 int sourceColumn)

Forrest-Tomlin update reading the new column directly from a CSC matrix.

Parameters:

specifiedColumn - The basis position being replaced

matrix - The full constraint matrix in CSC format

sourceColumn - The column index in the CSC matrix to read

Returns:

true if the update succeeded

checkSolvability

protected boolean checkSolvability()

isComputed

public final boolean isComputed()

Specified by:

isComputed in interface MatrixDecomposition<N extends Comparable<N>>

Returns:

true if decomposition has been attemped and was successful; false if not.

See Also:

• MatrixDecomposition.decompose(Access2D.Collectable)

reset

public void reset()

Description copied from interface: MatrixDecomposition

Delete computed results, and resets attributes to default values

Specified by:

reset in interface MatrixDecomposition<N extends Comparable<N>>