SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.qr

Class HouseholderQR

• java.lang.Object
• com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.qr.HouseholderQR
• All Implemented Interfaces:
QRDecomposition

public class HouseholderQR
extends Object
implements QRDecomposition
Successive Householder reflections gradually transform a matrix A to the upper triangular form. For example, the first step is to multiply A with a Householder matrix Q1 so that matrix Q1 * A has zeros in the left column (except for the first row). That is, $Q_1 \times A = \begin{bmatrix} a_1 & * & ... & * \\ 0 & & & \\ ... & & & \\ ... & & A' & \\ ... & & & \\ 0 & & & \end{bmatrix}$ At the end,$$Q_n \times ... \times Q_1 \times A = R$$ where R is upper triangular.

Householder reflection has a better numerical stability than the Gram-Schmidt process.

Wikipedia: Using Householder reflections
• Constructor Summary

Constructors
Constructor and Description
HouseholderQR(Matrix A)
Runs the Householder reflection process to orthogonalize a matrix.
HouseholderQR(Matrix A, double epsilon)
Runs the Householder reflection process to orthogonalize a matrix.
• Method Summary

All Methods
Modifier and Type Method and Description
HouseholderReflection[] getHouseholderMatrices()
Gets the householder reflections used in the reflection.
PermutationMatrix P()
Gets P, the pivoting matrix in the QR decomposition.
Matrix Q()
Gets the Q matrix in the QR decomposition.
UpperTriangularMatrix R()
Get the upper triangular matrix R in the QR decomposition, A = QR.
int rank()
Computes the rank by counting the number of non-zero rows in R.
Matrix squareQ()
Get the square Q matrix.
Matrix tallR()
Get the tall R matrix.
• Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• Constructor Detail

• HouseholderQR

public HouseholderQR(Matrix A,
double epsilon)
Runs the Householder reflection process to orthogonalize a matrix.
Parameters:
A - a matrix, where the number of rows ≥ the number of columns
epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0
Throws:
IllegalArgumentException - if the number of rows < the number of columns
• HouseholderQR

public HouseholderQR(Matrix A)
Runs the Householder reflection process to orthogonalize a matrix.
Parameters:
A - a matrix, where the number of rows ≥ the number of columns
• Method Detail

• Q

public Matrix Q()
Gets the Q matrix in the QR decomposition. The dimension of Q is nRows x nCols. $\begin{array}{lcl} Q_n \times ... \times Q_3 \times Q_2 \times Q_1 \times A = R \\ A = [Q_n \times ... \times Q_3 \times Q_2 \times Q_1]^{-1} \times R \\ = [Q_1^{-1} \times Q_2^{-1} \times ... \times Q_n^{-1}] \times R \\ = [Q_1 \times Q_2 \times ... \times Q_n] \times R \\ Q = Q_1 \times Q_2 \times ... \times Q_n \end{array}$ $$Q_1^{-1} = Q_1$$ , by the unitary property of Householder matrix

This implementation does not compute Q by explicitly doing this multiplication. Instead, we improve the performance by applying Qi's repeatedly on an identity matrix.

Specified by:
Q in interface QRDecomposition
Returns:
Q
• R

public UpperTriangularMatrix R()
Description copied from interface: QRDecomposition
Get the upper triangular matrix R in the QR decomposition, A = QR. The dimension of R is n x n, a square matrix.
Specified by:
R in interface QRDecomposition
Returns:
R
• P

public PermutationMatrix P()
Gets P, the pivoting matrix in the QR decomposition. Householder process does not need pivoting. Hence, P is always an identity matrix.
Specified by:
P in interface QRDecomposition
Returns:
an identity matrix
• rank

public int rank()
Computes the rank by counting the number of non-zero rows in R.

Note that Q may have more columns than the rank. The user should interpret the result with caution.

Specified by:
rank in interface QRDecomposition
Returns:
the rank
• squareQ

public Matrix squareQ()
Description copied from interface: QRDecomposition
Get the square Q matrix. This is an arbitrary orthogonal completion of the Q matrix in the QR decomposition. The dimension is m x m (square). We have A = sqQ * tallR.
Specified by:
squareQ in interface QRDecomposition
Returns:
the square Q matrix
• tallR

public Matrix tallR()
Description copied from interface: QRDecomposition
Get the tall R matrix. This is completed by binding zero rows beneath the square upper triangular matrix R in the QR decomposition. The dimension is m x n. It may not be square. We have A = sqQ * tallR.
Specified by:
tallR in interface QRDecomposition
Returns:
the tall R matrix
• getHouseholderMatrices

public HouseholderReflection[] getHouseholderMatrices()
Gets the householder reflections used in the reflection.
Returns:
the householder reflections used in the reflection