Module ojalgo

Package org.ojalgo.matrix.decomposition

Class FletcherMatthews

java.lang.Object

org.ojalgo.matrix.decomposition.FletcherMatthews

abstract class FletcherMatthews
extends java.lang.Object

Implements the Fletcher-Matthews form preserving method for LU factorization updates.

This algorithm is a variation of the Bartels-Golub-Reid method that preserves the form of the matrices during column updates. Key characteristics:

• Preserves the triangular structure of L and U matrices
• Handles column updates efficiently by tracking the last non-zero row
• Performs row and column exchanges to maintain numerical stability
• Updates both L and U matrices to reflect the changes
• Maintains the relationship L*U = P*A*Q where P and Q are permutation matrices

The algorithm works by:

1. Applying forward substitution to transform the new column
2. Finding the last non-zero row in the transformed column
3. Performing column exchanges to position the column correctly
4. Applying row exchanges and updates to maintain triangular form
5. Updating both L and U matrices to reflect all changes

This method is particularly effective for maintaining the structure of sparse matrices during updates, as it minimizes fill-in and preserves sparsity patterns.

Field Summary

Fields

Modifier and Type	Field	Description
private static boolean	DEBUG
(package private) static NumberContext	PRECISION
(package private) static NumberContext	SAFE

Constructor Summary

Constructors

Constructor	Description
FletcherMatthews()

Method Summary

Modifier and Type	Method	Description
(package private) static <N extends java.lang.Comparable<N>> boolean	update(Pivot rowOrder, PhysicalStore<N> combined, Pivot colOrder, int columnIndex, Access1D.Collectable<N,? super TransformableRegion<N>> column, PhysicalStore<N> preallocated)	Updates the LU decomposition when a column is modified in the original matrix.

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

PRECISION

static final NumberContext PRECISION

SAFE

static final NumberContext SAFE

Constructor Detail

FletcherMatthews

FletcherMatthews()

Method Detail

update

static <N extends java.lang.Comparable<N>> boolean update(Pivot rowOrder,
                                                          PhysicalStore<N> combined,
                                                          Pivot colOrder,
                                                          int columnIndex,
                                                          Access1D.Collectable<N,? super TransformableRegion<N>> column,
                                                          PhysicalStore<N> preallocated)

Updates the LU decomposition when a column is modified in the original matrix. This version is used when L and U are stored in a combined format.

Parameters:

rowOrder - Current row permutation vector

combined - Matrix storing both L and U factors in a combined format

colOrder - Current column permutation vector

col - Index of the column being updated

column - New column values

preallocated - Preallocated workspace for calculations

Returns:

true if the update was successful, false if the matrix became singular or numerically unstable