Class UnitaryDecomposition<T extends MatrixMixin<T,?,?,?>,U>
- Type Parameters:
T
- Type of the matrix to be decomposed.U
- Internal storage datatype of the matrix.
- Direct Known Subclasses:
ComplexUnitaryDecomposition
,RealUnitaryDecomposition
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
FieldsModifier and TypeFieldDescriptionprotected boolean
Flag indicating if a Householder reflector was needed for the current column meaning thetransformMatrix
should be updated.protected U
For storing a Householder vectors.protected int
The upper bound (exclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form.protected int
The lower bound (inclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form.final boolean
Flag indicating if the decomposition should be done in-place.protected int
The minimum of rows and columns in the matrix to be decomposed.protected int
Number of columns intransformMatrix
.protected int
Number of rows intransformMatrix
.protected U
Storage of the scalar factors for the Householder reflectors used in the decomposition.protected boolean
Flag indicating ifQ
should be computed in the decomposition from the reflectors applied.protected final int
Sub-diagonal of the upper quasi-triangular matrix.protected U
Pointer to the internal data array oftransformMatrix
.Storage for the upper triangular/Hessenburg matrix and the vectors of the Householder reflectors used in the decomposition.protected U
For temporarily storage when applying Householder vectors.Fields inherited from class org.flag4j.linalg.decompositions.Decomposition
hasDecomposed
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
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 TypeMethodDescriptionprotected 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 columnj
at and below thej
th row of the matrix to be decomposed.Applies the unitary decomposition to the matrix.Applies the unitary decomposition to the matrix.protected abstract double
findMaxAndInit
(int j) abstract T
getQ()
Gets the unitaryQ
matrix from the decomposition.abstract T
getUpper()
Gets the upper triangular/Hessenburg matrix from the last decomposition.protected abstract T
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
Initializes storage and other parameters for the decomposition.protected abstract void
updateData
(int j) Updates thetransformMatrix
matrix using the computed Householder vector fromcomputeHouseholder(int)
.Methods inherited from class org.flag4j.linalg.decompositions.Decomposition
ensureHasDecomposed
-
Field Details
-
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
Pointer to the internal data array oftransformMatrix
. -
numRows
protected int numRowsNumber of rows intransformMatrix
. -
numCols
protected int numColsNumber of columns intransformMatrix
. -
iLow
protected int iLowThe lower bound (inclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form. -
iHigh
protected int iHighThe upper bound (exclusive) of the row/column indices of the block matrix to reduce to quasi-triangular form. -
qFactors
Storage of the scalar factors for the Householder reflectors used in the decomposition. -
householderVector
For storing a Householder vectors. -
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 minAxisSizeThe minimum of rows and columns in the matrix to be decomposed. -
subDiagonal
protected final int subDiagonalSub-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 applyUpdateFlag indicating if a Householder reflector was needed for the current column meaning thetransformMatrix
should be updated. -
storeReflectors
protected boolean storeReflectorsFlag indicating ifQ
should be computed in the decomposition from the reflectors applied.- If
true
, thenQ
will be computed. - If
false
, thenQ
will not be computed.
- If
-
inPlace
public final boolean inPlaceFlag 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.
- If
-
-
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 ifQ
should be computed in the decomposition from the reflectors applied.- If
true
, thenQ
will be computed. - If
false
, thenQ
will not be computed.
- If
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.
- If
- Throws:
IllegalArgumentException
- If1 < subDiagonal < 0
.
-
-
Method Details
-
decompose
Applies the unitary decomposition to the matrix. Note, the full computation ofQ
is deferred untilgetQ()
is explicitly called.- Specified by:
decompose
in classDecomposition<T extends MatrixMixin<T,
?, ?, ?>> - Parameters:
src
- The source matrix to decompose.- Returns:
- A reference to this decomposer.
-
decompose
Applies the unitary decomposition to the matrix. Note, the full computation ofQ
is deferred untilgetQ()
is explicitly called.- Parameters:
src
- The source matrix to decompose.
-
getQ
Gets the unitaryQ
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
Creates and initializes Q to the appropriately sized identity matrix.- Returns:
- An identity matrix with the appropriate size.
-
getUpper
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
Gets the upper triangular/Hessenburg matrix from the last decomposition.- Returns:
- The upper triangular/Hessenburg matrix from the last decomposition.
-
setUp
Initializes storage and other parameters for the decomposition.- Parameters:
src
- Source matrix to be decomposed. IfinPlace == 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 columnj
below rowj
.
-
updateData
protected abstract void updateData(int j) Updates thetransformMatrix
matrix using the computed Householder vector fromcomputeHouseholder(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 columnj
at and below thej
th 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 thej
th 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 intransformMatrix
at columnj
at or below thej
th row. This method also initializes the firstnumRows-j
data of the storage arrayhouseholderVector
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 columnj
at or below thej
th row.
-