Module ojalgo

Package org.ojalgo.optimisation.linear

Class DecomposedInverse

java.lang.Object

org.ojalgo.optimisation.linear.DecomposedInverse

All Implemented Interfaces:

InvertibleFactor<java.lang.Double>, BasisRepresentation, Structure1D, Structure2D

final class DecomposedInverse
extends java.lang.Object
implements BasisRepresentation

Maintains an LU decomposition of the basis matrix for efficient solving of linear systems in the revised simplex method. Supports incremental updates using the Forrest-Tomlin algorithm when columns change, with periodic refactorization to maintain numerical stability.

Nested Class Summary

Nested classes/interfaces inherited from interface org.ojalgo.matrix.transformation.InvertibleFactor

InvertibleFactor.IdentityFactor<N extends java.lang.Comparable<N>>

Nested classes/interfaces inherited from interface org.ojalgo.structure.Structure1D

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

Nested classes/interfaces inherited from interface org.ojalgo.structure.Structure2D

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

Field Summary

Fields

Modifier and Type	Field	Description
private LU<java.lang.Double>	myDecomposition
private int	myUpdateCounter
private static int	UPDATES_LIMIT	Maximum number of updates before forcing a complete refactorization to prevent numerical instability from accumulated roundoff errors.

Constructor Summary

Constructors

Constructor	Description
DecomposedInverse(boolean sparse, int dim)	Creates a new decomposition-based basis representation.

Method Summary

Modifier and Type	Method	Description
void	btran(double[] arg)
void	btran(PhysicalStore<java.lang.Double> arg)	Solves the transposed system B^T x = b, overwriting the right-hand side with the solution.
void	ftran(double[] arg)
void	ftran(PhysicalStore<java.lang.Double> arg)	Solves the system B x = b, overwriting the right-hand side with the solution.
int	getColDim()
int	getRowDim()
void	reset(MatrixStore<java.lang.Double> basis)	Completely rebuilds the decomposition from the given basis matrix.
void	update(MatrixStore<java.lang.Double> basis, int col, SparseArray<java.lang.Double> values)	Updates the decomposition to reflect a change in the basis matrix.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.ojalgo.structure.Structure2D

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

Field Detail

UPDATES_LIMIT

private static final int UPDATES_LIMIT

Maximum number of updates before forcing a complete refactorization to prevent numerical instability from accumulated roundoff errors.

See Also:

Constant Field Values

myDecomposition

private final LU<java.lang.Double> myDecomposition

myUpdateCounter

private int myUpdateCounter

Constructor Detail

DecomposedInverse

DecomposedInverse(boolean sparse,
                  int dim)

Creates a new decomposition-based basis representation.

Parameters:

sparse - Whether to use sparse LU decomposition (recommended for larger sparse problems)

dim - Dimension of the basis matrix

Method Detail

btran

public void btran(double[] arg)

Specified by:

btran in interface InvertibleFactor<java.lang.Double>

See Also:

InvertibleFactor.IdentityFactor.btran(PhysicalStore)

btran

public void btran(PhysicalStore<java.lang.Double> arg)

Solves the transposed system B^T x = b, overwriting the right-hand side with the solution. Used to compute dual variables (shadow prices) in the simplex method.

Specified by:

btran in interface InvertibleFactor<java.lang.Double>

Parameters:

arg - [b] transformed into [x]

ftran

public void ftran(double[] arg)

Specified by:

ftran in interface InvertibleFactor<java.lang.Double>

See Also:

InvertibleFactor.IdentityFactor.ftran(PhysicalStore)

ftran

public void ftran(PhysicalStore<java.lang.Double> arg)

Solves the system B x = b, overwriting the right-hand side with the solution. Used to compute the basic solution and direction vectors in the simplex method.

Specified by:

ftran in interface InvertibleFactor<java.lang.Double>

Parameters:

arg - [b] transformed into [x]

getColDim

public int getColDim()

Specified by:

getColDim in interface Structure2D

Returns:

The number of columns

getRowDim

public int getRowDim()

Specified by:

getRowDim in interface Structure2D

Returns:

The number of rows

reset

public void reset(MatrixStore<java.lang.Double> basis)

Completely rebuilds the decomposition from the given basis matrix. Resets the update counter.

Specified by:

reset in interface BasisRepresentation

update

public void update(MatrixStore<java.lang.Double> basis,
                   int col,
                   SparseArray<java.lang.Double> values)

Updates the decomposition to reflect a change in the basis matrix. Uses the Forrest-Tomlin update algorithm to efficiently modify the LU factors. Falls back to a complete refactorization if: 1. The update counter exceeds the limit 2. The decomposition is not in a computed state 3. The update operation fails due to numerical issues

Specified by:

update in interface BasisRepresentation

Parameters:

basis - The current basis matrix (used only if refactorization is needed)

col - The column index in the basis being replaced

values - The new column values