Class SparseQDLDL

java.lang.Object

org.ojalgo.matrix.decomposition.AbstractDecomposition<Double, R064Store>

org.ojalgo.matrix.decomposition.SparseQDLDL

All Implemented Interfaces:

LDL<Double>, LDU<Double>, MatrixDecomposition<Double>, MatrixDecomposition.Determinant<Double>, MatrixDecomposition.Hermitian<Double>, MatrixDecomposition.Ordered<Double>, MatrixDecomposition.Pivoting<Double>, MatrixDecomposition.RankRevealing<Double>, MatrixDecomposition.Solver<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 SparseQDLDL
extends AbstractDecomposition<Double, R064Store>
implements LDL<Double>

Quasi-Definite LDL (QDLDL) sparse decomposition.

Reference: https://github.com/osqp/qdldl

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	SparseQDLDL.EliminationTree	Symbolic elimination tree
private static final class	SparseQDLDL.WorkerCache

Nested classes/interfaces inherited from interface InvertibleFactor

InvertibleFactor.IdentityFactor<N>

Nested classes/interfaces inherited from interface LDL

LDL.Factory<N>, LDL.ModifiedFactory<N>

Nested classes/interfaces inherited from interface MatrixDecomposition

MatrixDecomposition.Determinant<N>, MatrixDecomposition.EconomySize<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

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

Modifier and Type	Field	Description
private double[]	myD
private double[]	myDinv
private R064CSC	myL
private int	myPositiveValuesInD
private final SparseQDLDL.WorkerCache	myWorkerCache

Fields inherited from interface LDL

C128, H256, Q128, R064, R128

Fields inherited from interface MatrixDecomposition

TYPICAL

Constructor Summary

Constructors

Constructor	Description
SparseQDLDL()

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()
private static SparseQDLDL.EliminationTree	computeEliminationTree(int n, int[] pointers, int[] indices)
SparseQDLDL.EliminationTree	computeEliminationTree(R064CSC matrix)
int	countSignificant(double threshold)
private boolean	decompose(R064CSC matrix, SparseQDLDL.EliminationTree eTree, R064CSC decomp, double[] D, double[] Dinv, SparseQDLDL.WorkerCache workers)	In this method, variable names are deliberately kept close to what they are in the original c-code.
boolean	decompose(Access2D.Collectable<Double, ? super TransformableRegion<Double>> matrix)
boolean	factor(R064CSC matrix)	Requirements on the input matrix and summary of the factorisation semantics: Square. Symmetric, with only the upper/right triangle stored.
boolean	factor(R064CSC matrix, SparseQDLDL.EliminationTree eTree)	Convenience for callers that have already computed the symbolic structure for a given sparsity pattern.
void	ftran(double[] x)	Solve A x = b in-place for one column/vector x.
void	ftran(PhysicalStore<Double> arg)	Forward-transformation
private static void	ftranD(double[] inv, double[] x)
private static void	ftranL(int[] pointers, int[] indices, double[] values, double[] x)
private static void	ftranU(int[] pointers, int[] indices, double[] values, double[] x)
int	getColDim()
MatrixStore<Double>	getD()
Double	getDeterminant()	Determinant of the factorised matrix.
MatrixStore<Double>	getInverse(PhysicalStore<Double> preallocated)	Implementing this method is optional.
MatrixStore<Double>	getL()	Must implement either LDL.getL() or LDL.getR().
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>	invert(Access2D<?> original, PhysicalStore<Double> preallocated)	Exactly how (if at all) a specific implementation makes use of preallocated is not specified by this interface.
boolean	isPivoted()
boolean	isSolvable()	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.
PhysicalStore<Double>	preallocate(int nbEquations, int nbVariables, int nbSolutions)
double[]	solve(double[] b)	Solve A x = b
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.

Methods inherited from class AbstractDecomposition

aggregator, applyPivotOrder, applyReverseOrder, collect, computed, copyColumn, copyRow, function, getDimensionalEpsilon, isAspectRatioNormal, isComputed, makeArray, makeDiagonal, makeEye, makeHouseholder, makeIdentity, makeRotation, makeRotation, makeZero, makeZero, reset, scalar, wrap

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 LDL

getR, reconstruct

Methods inherited from interface LDU

isOrdered

Methods inherited from interface MatrixDecomposition

isComputed, reset

Methods inherited from interface MatrixDecomposition.Determinant

toDeterminantProvider

Methods inherited from interface MatrixDecomposition.Hermitian

checkAndDecompose

Methods inherited from interface MatrixDecomposition.Pivoting

decomposeWithoutPivoting

Methods inherited from interface MatrixDecomposition.RankRevealing

getRank, isFullRank

Methods inherited from interface MatrixDecomposition.Solver

compute, getInverse, getSolution, 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

Field Details

myD

private double[] myD

myDinv

private double[] myDinv

myL

private R064CSC myL

myPositiveValuesInD

private int myPositiveValuesInD

myWorkerCache

private final SparseQDLDL.WorkerCache myWorkerCache

Constructor Details

SparseQDLDL

public SparseQDLDL()

Method Details

computeEliminationTree

private static SparseQDLDL.EliminationTree computeEliminationTree(int n,
 int[] pointers,
 int[] indices)

ftranD

private static void ftranD(double[] inv,
 double[] x)

ftranL

private static void ftranL(int[] pointers,
 int[] indices,
 double[] values,
 double[] x)

ftranU

private static void ftranU(int[] pointers,
 int[] indices,
 double[] values,
 double[] x)

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>

computeEliminationTree

public SparseQDLDL.EliminationTree computeEliminationTree(R064CSC matrix)

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)

Requirements on the input matrix and summary of the factorisation semantics:

• Square.
• Symmetric, with only the upper/right triangle stored. The lower/left triangle is not ignored; any explicitly stored non-zero entries there will cause the symbolic phase to fail.
• Sparse (not strictly required, but this implementation is optimised for sparse structure).
• Quasi-definite for a fully solvable system: during factorisation the diagonal entries D[i] are classified relative to a small, scale-dependent tolerance derived from the largest |D[i]| seen so far and the dimensional epsilon. All D[i] must be classified as positive for isSolvable() to return true.

The underlying QDLDL-style algorithm will return false if any diagonal entry in D is classified as (numerically) zero. Indefinite or near-singular matrices may still factorise, but will typically yield isSolvable() == false and are not suitable for use as quasi-definite systems when solving or inverting.

This method performs both the symbolic analysis (elimination tree) and numeric factorisation. For repeated factorisations with identical sparsity patterns and updated values, callers may instead use factor(R064CSC, EliminationTree) together with a cached symbolic tree obtained from

invalid reference

#getSymbolic()

.

factor

public boolean factor(R064CSC matrix,
 SparseQDLDL.EliminationTree eTree)

Convenience for callers that have already computed the symbolic structure for a given sparsity pattern. The caller is responsible for ensuring that the supplied SparseQDLDL.EliminationTree matches the pattern of matrix; behaviour is undefined if they do not.

ftran

public void ftran(double[] x)

Solve A x = b in-place for one column/vector x. Initially x holds b, on exit x holds the solution.

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

getD

public MatrixStore<Double> getD()

Specified by:

getD in interface LDL<Double>

getDeterminant

public Double getDeterminant()

Determinant of the factorised matrix.

With no pivoting the determinant is computed as the product of the diagonal entries of D returned by the LDL factorisation. For a quasi-definite input (all diagonal entries classified as positive according to the internal tolerance) isSolvable() is true and the determinant is strictly positive. For general symmetric or indefinite inputs the determinant may be negative or close to zero and should be interpreted with care. If the factorisation has not been computed this method returns NaN.

Specified by:

getDeterminant in interface MatrixDecomposition.Determinant<Double>

Specified by:

getDeterminant in interface Provider2D.Determinant<Double>

Returns:

The matrix' determinant

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

Description copied from interface: LDL

Must implement either LDL.getL() or LDL.getR().

Specified by:

getL in interface LDL<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

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>

Overrides:

isSolvable in class AbstractDecomposition<Double, R064Store>

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

solve

public double[] solve(double[] b)

Solve A x = b

decompose

private boolean decompose(R064CSC matrix,
 SparseQDLDL.EliminationTree eTree,
 R064CSC decomp,
 double[] D,
 double[] Dinv,
 SparseQDLDL.WorkerCache workers)

In this method, variable names are deliberately kept close to what they are in the original c-code.

checkSolvability

protected boolean checkSolvability()

Overrides:

checkSolvability in class AbstractDecomposition<Double, R064Store>