Class LU<T extends MatrixMixin<T,?,?,?>>

java.lang.Object
org.flag4j.linalg.decompositions.Decomposition<T>
org.flag4j.linalg.decompositions.lu.LU<T>
Type Parameters:
T - The type of matrix on which LU decomposition is performed.
Direct Known Subclasses:
ComplexLU, FieldLU, RealLU
public abstract class LU<T extends MatrixMixin<T,?,?,?>> extends Decomposition<T>

An abstract base class for LU decomposition of a matrix.

The LU decomposition decomposes a matrix A into the product of a unit-lower triangular matrix L and an upper triangular matrix U, such that: \[ A = LU \]

Pivoting Strategies:

Pivoting may be used to improve the stability of the decomposition. Pivoting involves swapping rows and/or columns within the matrix during decomposition.

This class supports three pivoting strategies via the LU.Pivoting enum:

  • LU.Pivoting.NONE: No pivoting is performed. This pivoting strategy is generally not recommended. \[ A = LU \]
  • LU.Pivoting.PARTIAL: Only row pivoting is performed to improve numerical stability. Generally, this is the preferred pivoting strategy. The decomposition then becomes, \[ PA = LU \]
    • where P is a permutation matrix representing the row swaps.
  • LU.Pivoting.FULL: Both row and column pivoting are performed to enhance numerical robustness. The decomposition then becomes, \[ PAQ = LU \] where P and Q are permutation matrices representing the row and column swaps respectively.

    Full pivoting may be useful for highly ill-conditioned matrices but, for practical purposes, partial pivoting is generally sufficient and more performant.

Storage Format:

The computed LU decomposition is stored within a single matrix LU, where:
  • The upper triangular part (including the diagonal) represents the non-zero values of U.
  • The strictly lower triangular part represents the non-zero, non-diagonal values of L. Since L is unit-lower triangular, the diagonal is not stored as it is known to be all zeros.

Usage:

The decomposition workflow typically follows these steps:
  1. Instantiate a concrete subclass of LU.
  2. Call decompose(MatrixMixin) to perform the factorization.
  3. Retrieve the resulting matrices using getL(), getU(), getP(), and getQ().

Implementation Notes:

Subclasses must implement the specific pivoting strategies by defining:

See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    LU.Pivoting
    Simple enum containing pivoting options for pivoting in LU decomposition.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int[]
    colSwaps
    Array to track column swaps made with full pivoting.
    protected final boolean
    inPlace
    Flag indicating if the decomposition should be done in/out-of-place.
    protected T
    LU
    Storage for L and U matrices.
    protected int
    numColSwaps
    Tracks the number of column swaps made during full pivoting.
    protected int
    numRowSwaps
    Tracks the number of row swaps made during partial/full pivoting.
    protected PermutationMatrix
    P
    Permutation matrix to store row swaps if partial pivoting is used.
    final LU.Pivoting
    pivotFlag
    Flag indicating what pivoting to use.
    protected PermutationMatrix
    Q
    Permutation matrix to store column swaps if full pivoting is used.
    protected int[]
    rowSwaps
    Array to track row swaps made with full/partial pivoting.
    protected static final String
    ZERO_PIV_ERR
    Error message for when a zero pivot is encountered.

    Fields inherited from class org.flag4j.linalg.decompositions.Decomposition

    hasDecomposed

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    LU(LU.Pivoting pivoting, boolean inPlace)
    Constructs a LU decomposer with the specified pivoting.

  • Method Summary

    Modifier and Type
    Method
    Description
    LU<T>
    decompose(T src)
    Applies LU decomposition to the source matrix using the pivoting specified in the constructor.
    protected abstract void
    fullPivot()
    Computes the LU decomposition using full/rook pivoting (i.e. row and column swapping).
    abstract T
    getL()
    Gets the unit lower triangular matrix of the decomposition.
    T
    getLU()
    Gets the L and U matrices of the decomposition combined in a single matrix.
    int
    getNumColSwaps()
    Gets the number of column swaps used in the last decomposition.
    int
    getNumRowSwaps()
    Gets the number of row swaps used in the last decomposition.
    PermutationMatrix
    getP()
    Gets the row permutation matrix of the decomposition.
    PermutationMatrix
    getQ()
    Gets the column permutation matrix of the decomposition.
    abstract T
    getU()
    Gets the upper triangular matrix of the decomposition.
    protected void
    initLU(T src)
    Initializes the LU matrix by copying the source matrix to decompose.
    protected abstract void
    noPivot()
    Computes the LU decomposition using no pivoting (i.e. rows and columns are not swapped).
    protected abstract void
    partialPivot()
    Computes the LU decomposition using partial pivoting (i.e. row swapping).
    protected void
    swapCols(int colIdx1, int colIdx2)
    Tracks the swapping of two columns during gaussian elimination with full pivoting.
    protected void
    swapRows(int rowIdx1, int rowIdx2)
    Tracks the swapping of two rows during gaussian elimination with partial or full pivoting.

    Methods inherited from class org.flag4j.linalg.decompositions.Decomposition

    ensureHasDecomposed

    Methods inherited from class java.lang.Object

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

  • Field Details

    • ZERO_PIV_ERR

      protected static final String ZERO_PIV_ERR
      Error message for when a zero pivot is encountered.
      See Also:

    • pivotFlag

      public final LU.Pivoting pivotFlag
      Flag indicating what pivoting to use.

    • inPlace

      protected final boolean inPlace
      Flag indicating if the decomposition should be done in/out-of-place.
      • If true, then the decomposition will be done in-place.
      • If true, then the decomposition will be done out-of-place.

    • LU

      protected T extends MatrixMixin<T,?,?,?> LU

      Storage for L and U matrices. Stored in a single matrix.

      The upper triangular portion of LU, including the diagonal, stores the non-zero values of U while the lower triangular portion, excluding the diagonal, stores the non-zero, non-diagonal values of L. Since L is unit-lower triangular, the diagonal need not be stored as it is known to be all ones.

    • P

      protected PermutationMatrix P
      Permutation matrix to store row swaps if partial pivoting is used.

    • Q

      protected PermutationMatrix Q
      Permutation matrix to store column swaps if full pivoting is used.

    • numRowSwaps

      protected int numRowSwaps
      Tracks the number of row swaps made during partial/full pivoting.

    • numColSwaps

      protected int numColSwaps
      Tracks the number of column swaps made during full pivoting.

    • rowSwaps

      protected int[] rowSwaps
      Array to track row swaps made with full/partial pivoting.

    • colSwaps

      protected int[] colSwaps
      Array to track column swaps made with full pivoting.

  • Constructor Details

    • LU

      protected LU(LU.Pivoting pivoting, boolean inPlace)
      Constructs a LU decomposer with the specified pivoting.
      Parameters:
      pivoting - Pivoting to use.
      inPlace - Flag indicating if the decomposition should be done in/out-of-place.
      • If true, then the decomposition will be done in-place.
      • If true, then the decomposition will be done out-of-place.

  • Method Details

    • decompose

      public LU<T> decompose(T src)
      Applies LU decomposition to the source matrix using the pivoting specified in the constructor.
      Specified by:
      decompose in class Decomposition<T extends MatrixMixin<T,?,?,?>>
      Parameters:
      src - The source matrix to decompose. If inPlace was true in the constructor then this matrix will be modified.
      Returns:
      A reference to this decomposer.

    • initLU

      protected void initLU(T src)
      Initializes the LU matrix by copying the source matrix to decompose.
      Parameters:
      src - Source matrix to decompose.

    • noPivot

      protected abstract void noPivot()
      Computes the LU decomposition using no pivoting (i.e. rows and columns are not swapped).

    • partialPivot

      protected abstract void partialPivot()
      Computes the LU decomposition using partial pivoting (i.e. row swapping).

    • fullPivot

      protected abstract void fullPivot()
      Computes the LU decomposition using full/rook pivoting (i.e. row and column swapping).

    • getLU

      public T getLU()
      Gets the L and U matrices of the decomposition combined in a single matrix.
      Returns:
      The L and U matrices of the decomposition stored together in a single matrix. The diagonal of L is all ones and is not stored allowing the diagonal of U to be stored along the diagonal of the combined matrix.
      Throws:
      IllegalStateException - If this method is called before decompose(MatrixMixin).

    • getL

      public abstract T getL()
      Gets the unit lower triangular matrix of the decomposition.
      Returns:
      The unit lower triangular matrix of the decomposition.
      Throws:
      IllegalStateException - If this method is called before decompose(MatrixMixin).

    • getU

      public abstract T getU()
      Gets the upper triangular matrix of the decomposition.
      Returns:
      The upper triangular matrix of the decomposition.
      Throws:
      IllegalStateException - If this method is called before decompose(MatrixMixin).

    • getP

      public PermutationMatrix getP()
      Gets the row permutation matrix of the decomposition.
      Returns:
      The row permutation matrix of the decomposition. If no pivoting was used, null will be returned.
      Throws:
      IllegalStateException - If this method is called before decompose(MatrixMixin).

    • getQ

      public PermutationMatrix getQ()
      Gets the column permutation matrix of the decomposition.
      Returns:
      The column permutation matrix of the decomposition. If full pivoting was not used, null will be returned.
      Throws:
      IllegalStateException - If this method is called before decompose(MatrixMixin).

    • getNumRowSwaps

      public int getNumRowSwaps()
      Gets the number of row swaps used in the last decomposition.
      Returns:
      The number of row swaps used in the last decomposition.
      Throws:
      IllegalStateException - If this method is called before decompose(MatrixMixin).

    • getNumColSwaps

      public int getNumColSwaps()
      Gets the number of column swaps used in the last decomposition.
      Returns:
      The number of column swaps used in the last decomposition.
      Throws:
      IllegalStateException - If this method is called before decompose(MatrixMixin).

    • swapRows

      protected void swapRows(int rowIdx1, int rowIdx2)
      Tracks the swapping of two rows during gaussian elimination with partial or full pivoting.
      Parameters:
      rowIdx1 - First row index in swap.
      rowIdx2 - Second row index in swap.

    • swapCols

      protected void swapCols(int colIdx1, int colIdx2)
      Tracks the swapping of two columns during gaussian elimination with full pivoting.
      Parameters:
      colIdx1 - First column index in swap.
      colIdx2 - Second column index in swap.