Class UnitaryDecomposition<T extends MatrixMixin<T,?,?,?>,U>

java.lang.Object
org.flag4j.linalg.decompositions.Decomposition<T>
org.flag4j.linalg.decompositions.unitary.UnitaryDecomposition<T,U>
Type Parameters:
T - Type of the matrix to be decomposed.
U - Internal storage datatype of the matrix.
Direct Known Subclasses:
ComplexUnitaryDecomposition, RealUnitaryDecomposition
public abstract class UnitaryDecomposition<T extends MatrixMixin<T,?,?,?>,U> extends Decomposition<T>

This class is the base class for all decompositions which proceed by using unitary transformations (specifically Householder reflectors) to bring a matrix into an upper triangular matrix (QR decomposition) or an upper Hessenburg matrix (Hessenburg decomposition).

This class is provided because both the QR and Hessenburg decompositions proceed by very similar computations resulting in a substantial amount of overlap in the implementations of the two decompositions. This class serves to implement these common computations such that implementations of either decomposition may utilize them without the need of reimplementing them.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected boolean
    applyUpdate
    Flag indicating if a Householder reflector was needed for the current column meaning the transformMatrix should be updated.
    protected U
    householderVector
    For storing a Householder vectors.
    protected int
    iHigh
    The upper bound (exclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form.
    protected int
    iLow
    The lower bound (inclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form.
    final boolean
    inPlace
    Flag indicating if the decomposition should be done in-place.
    protected int
    minAxisSize
    The minimum of rows and columns in the matrix to be decomposed.
    protected int
    numCols
    Number of columns in transformMatrix.
    protected int
    numRows
    Number of rows in transformMatrix.
    protected U
    qFactors
    Storage of the scalar factors for the Householder reflectors used in the decomposition.
    protected boolean
    storeReflectors
    Flag indicating if Q should be computed in the decomposition from the reflectors applied.
    protected final int
    subDiagonal
    Sub-diagonal of the upper quasi-triangular matrix.
    protected U
    transformData
    Pointer to the internal data array of transformMatrix.
    T
    transformMatrix
    Storage for the upper triangular/Hessenburg matrix and the vectors of the Householder reflectors used in the decomposition.
    protected U
    workArray
    For temporarily storage when applying Householder vectors.

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

    hasDecomposed

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    UnitaryDecomposition(int subDiagonal, boolean storeReflectors, boolean inPlace)
    Creates a real unitary decomposer which will reduce the matrix to an upper quasi-triangular matrix (Either truly upper or upper Hessenburg).

  • Method Summary

    Modifier and Type
    Method
    Description
    protected abstract void
    computeHouseholder(int j)
    Computes the Householder vector for the first column of the sub-matrix with upper left corner at (j, j).
    protected abstract void
    computePhasedNorm(int j, double maxAbs)
    Computes the norm of column j at and below the jth row of the matrix to be decomposed.
    UnitaryDecomposition<T,U>
    decompose(T src)
    Applies the unitary decomposition to the matrix.
    UnitaryDecomposition<T,U>
    decompose(T src, int iLow, int iHigh)
    Applies the unitary decomposition to the matrix.
    protected abstract double
    findMaxAndInit(int j)
    Finds the maximum value in transformMatrix at column j at or below the jth row.
    abstract T
    getQ()
    Gets the unitary Q matrix from the decomposition.
    abstract T
    getUpper()
    Gets the upper triangular/Hessenburg matrix from the last decomposition.
    protected abstract T
    getUpper(T U)
    Gets the upper triangular/Hessenburg matrix from the last decomposition.
    protected abstract T
    initQ()
    Creates and initializes Q to the appropriately sized identity matrix.
    protected abstract void
    initWorkArrays(int maxAxisSize)
    Initialized any work arrays to be used in computing the decomposition with the proper size.
    protected void
    setUp(T src)
    Initializes storage and other parameters for the decomposition.
    protected abstract void
    updateData(int j)
    Updates the transformMatrix matrix using the computed Householder vector from computeHouseholder(int).

    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

    • transformMatrix

      public T extends MatrixMixin<T,?,?,?> transformMatrix

      Storage for the upper triangular/Hessenburg matrix and the vectors of the Householder reflectors used in the decomposition.

      The upper triangular/Hessenburg will have all zeros below either the diagonal or the first sub-diagonal and will be stored in the top corner above that diagonal. For instance, if the quasi-triangular matrix is truly upper triangular, it will be stored at and above the principle diagonal. If the quasi-triangular matrix is upper Hessenburg, it will be stored at and above the first sub-diagonal.

      The Householder reflectors used to bring the original matrix to the upper triangular/Hessenburg form will be stored as the columns below the last non-zero sub-diagonal of the quasi-triangular matrix. The first value of each reflector is not stored but is assumed to be 1.

      This provides compact storage for decompositions which proceed by unitary transformations. Further, the full computation of the unitary matrix can be deferred until it is needed.

    • transformData

      protected U transformData
      Pointer to the internal data array of transformMatrix.

    • numRows

      protected int numRows
      Number of rows in transformMatrix.

    • numCols

      protected int numCols
      Number of columns in transformMatrix.

    • iLow

      protected int iLow
      The lower bound (inclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form.

    • iHigh

      protected int iHigh
      The upper bound (exclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form.

    • qFactors

      protected U qFactors
      Storage of the scalar factors for the Householder reflectors used in the decomposition.

    • householderVector

      protected U householderVector
      For storing a Householder vectors.

    • workArray

      protected U workArray
      For temporarily storage when applying Householder vectors. This is useful for avoiding unneeded garbage collection and for improving cache performance when traversing columns.

    • minAxisSize

      protected int minAxisSize
      The minimum of rows and columns in the matrix to be decomposed.

    • subDiagonal

      protected final int subDiagonal
      Sub-diagonal of the upper quasi-triangular matrix. That is, the sub0diagonal for which all data below will be zero in the final upper quasi-triangular matrix. Must be zero or one. If zero, it will be upper triangular. If one, it will be upper Hessenburg.

    • applyUpdate

      protected boolean applyUpdate
      Flag indicating if a Householder reflector was needed for the current column meaning the transformMatrix should be updated.

    • storeReflectors

      protected boolean storeReflectors
      Flag indicating if Q should be computed in the decomposition from the reflectors applied.
      • If true, then Q will be computed.
      • If false, then Q will not be computed.

    • inPlace

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

  • Constructor Details

    • UnitaryDecomposition

      protected UnitaryDecomposition(int subDiagonal, boolean storeReflectors, boolean inPlace)
      Creates a real unitary decomposer which will reduce the matrix to an upper quasi-triangular matrix (Either truly upper or upper Hessenburg).
      Parameters:
      subDiagonal - Sub-diagonal of the upper quasi-triangular matrix. Must be zero or one. If zero, it will be upper triangular. If one, it will be upper Hessenburg.
      storeReflectors - Flag indicating if Q should be computed in the decomposition from the reflectors applied.
      • If true, then Q will be computed.
      • If false, then Q will not be computed.
      inPlace - Flag indicating if the decomposition should be done in-place.
      • If true, then the decomposition will be done in place.
      • If false, then the decomposition will be done out-of-place.
      Throws:
      IllegalArgumentException - If 1 < subDiagonal < 0.

  • Method Details

    • decompose

      public UnitaryDecomposition<T,U> decompose(T src)
      Applies the unitary decomposition to the matrix. Note, the full computation of Q is deferred until getQ() is explicitly called.
      Specified by:
      decompose in class Decomposition<T extends MatrixMixin<T,?,?,?>>
      Parameters:
      src - The source matrix to decompose.
      Returns:
      A reference to this decomposer.

    • decompose

      public UnitaryDecomposition<T,U> decompose(T src, int iLow, int iHigh)
      Applies the unitary decomposition to the matrix. Note, the full computation of Q is deferred until getQ() is explicitly called.
      Parameters:
      src - The source matrix to decompose.

    • getQ

      public abstract T getQ()
      Gets the unitary Q matrix from the decomposition. This is the accumulation of all unitary transformation applied to bring the matrix to an upper triangular or Hessenburg form.
      Returns:
      The Q matrix from the decomposition. I.e. the accumulation of all unitary transformation applied during the decomposition.

    • initQ

      protected abstract T initQ()
      Creates and initializes Q to the appropriately sized identity matrix.
      Returns:
      An identity matrix with the appropriate size.

    • getUpper

      protected abstract T getUpper(T U)
      Gets the upper triangular/Hessenburg matrix from the last decomposition.
      Parameters:
      U - Storage for upper triangular/Hessenburg matrix. Assumed to be the zero matrix of an appropriate size.
      Returns:
      The upper triangular/Hessenburg matrix from the last decomposition.

    • getUpper

      public abstract T getUpper()
      Gets the upper triangular/Hessenburg matrix from the last decomposition.
      Returns:
      The upper triangular/Hessenburg matrix from the last decomposition.

    • setUp

      protected void setUp(T src)
      Initializes storage and other parameters for the decomposition.
      Parameters:
      src - Source matrix to be decomposed. If inPlace == true, this matrix will be modified.

    • initWorkArrays

      protected abstract void initWorkArrays(int maxAxisSize)
      Initialized any work arrays to be used in computing the decomposition with the proper size.
      Parameters:
      maxAxisSize - Length of the largest axis in the matrix to be decomposed. That is, Math.max(numRows, numCols).

    • computeHouseholder

      protected abstract void computeHouseholder(int j)
      Computes the Householder vector for the first column of the sub-matrix with upper left corner at (j, j).
      Parameters:
      j - Index of the upper left corner of the sub-matrix for which to compute the Householder vector for the first column. That is, a Householder vector will be computed for the portion of column j below row j.

    • updateData

      protected abstract void updateData(int j)
      Updates the transformMatrix matrix using the computed Householder vector from computeHouseholder(int).
      Parameters:
      j - Index of sub-matrix for which the Householder reflector was computed for.

    • computePhasedNorm

      protected abstract void computePhasedNorm(int j, double maxAbs)
      Computes the norm of column j at and below the jth row of the matrix to be decomposed. The norm will have the same parity as the first entry in the sub-column.
      Parameters:
      j - Column to compute norm of below the jth row.
      maxAbs - Maximum absolute value in the column. Used for scaling norm to minimize potential overflow issues.

    • findMaxAndInit

      protected abstract double findMaxAndInit(int j)
      Finds the maximum value in transformMatrix at column j at or below the jth row. This method also initializes the first numRows-j data of the storage array householderVector to the data of this column.
      Parameters:
      j - Index of column (and starting row) to compute max of.
      Returns:
      The maximum value in transformMatrix at column j at or below the jth row.