Class BiDiagonalizationByHouseholder

  • All Implemented Interfaces:
    BiDiagonalization

    public class BiDiagonalizationByHouseholder
    extends Object
    implements BiDiagonalization
    Given a tall (m x n) matrix A, where m ≥ n, we find orthogonal matrices U and V such that U' * A * V = B. B is an upper bi-diagonal matrix. That is, \[ U'AV = \begin{bmatrix} d_1 & f_1 & ... & & & \\ 0 & d_2 & f_2 & ... & & \\ 0 & ... & & & & \\ ... & & & & d_{n-1} & f_{n-1} \\ ... & & & & & d_n \\ 0 & ... & & & & 0 \\ & ... & & & & ... \\ 0 & ... & & & & 0 \end{bmatrix} \] This implementation uses the Householder reflection process to repeatedly zero out the columns and the rows (partially). For example, the first step is to left multiply A with the Householder matrix U1' so that matrix U1 * A has zeros in the left column (except for the first row). That is, \[ \begin{bmatrix} a_{1,1} & * & ... & * \\ 0 & & & \\ 0 & & & \\ ... & & A_1 & \\ ... & & & \\ 0 & & & \end{bmatrix} \] Then, we right multiply A with V1. (Note that the V's are Hermitian.) We have \[ U_1'AV_1 = \begin{bmatrix} a_{1,1} & a_{1,2} & 0 & ... & 0\\ 0 & & & & \\ 0 & & & & \\ ... & & A_2 & & \\ ... & & & & \\ 0 & & & & \end{bmatrix} \] In the end, (U1 * ... * Un)' * A * (V1 * ... * Vn) = B where B is upper bi-diagonal. The upper part of B, an n x n matrix, is a square, bi-diagonal matrix.

    This transformation always succeeds.

    • Constructor Detail

      • BiDiagonalizationByHouseholder

        public BiDiagonalizationByHouseholder​(Matrix A)
        Runs the Householder bi-diagonalization for a tall matrix.
        Parameters:
        A - a tall matrix
        Throws:
        IllegalArgumentException - if A is not tall
    • Method Detail

      • B

        public BidiagonalMatrix B()
        Gets B, which is the square upper part of U.t().multiply(A).multiply(V). The dimension of B is n x n.
        Specified by:
        B in interface BiDiagonalization
        Returns:
        B
      • U

        public Matrix U()
        Gets U, where U' = Uk * ... * U1, k = A.nCols() (or k = A.nCols() - 1 for square A). The dimension of U is m x m.

        To compute U, instead of explicitly doing this multiplication, this implementation improves the performance by applying Ui's repeatedly on an identity matrix. We take the transpose afterward.

        Specified by:
        U in interface BiDiagonalization
        Returns:
        the U matrix
      • V

        public Matrix V()
        Gets V, where V' = Vk * ... * V1, k = A.nCols() - 2. The dimension of V is n x n.

        To compute V, instead of explicitly doing this multiplication, this implementation improves the performance by applying Vi's repeatedly on an identity matrix. We take the transpose afterward.

        Specified by:
        V in interface BiDiagonalization
        Returns:
        the V matrix