Class 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.

    See Also:
    Wikipedia: Using Householder reflections
    • 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