Class BlockHouseHolder_DDRB

java.lang.Object
org.ejml.dense.block.decomposition.qr.BlockHouseHolder_DDRB

public class BlockHouseHolder_DDRB extends Object

Contains various helper functions for performing a block matrix QR decomposition.

Assumptions:

  • All submatrices are aligned along the inner blocks of the DMatrixRBlock.
  • Some times vectors are assumed to have leading zeros and a one.
  • Constructor Summary

    Constructors
    Constructor
    Description
     
  • Method Summary

    Modifier and Type
    Method
    Description
    static void
    add_row(int blockLength, DSubmatrixD1 A, int rowA, double alpha, DSubmatrixD1 B, int rowB, double beta, DSubmatrixD1 C, int rowC, int zeroOffset, int end)
     
    static boolean
    computeHouseHolderCol(int blockLength, DSubmatrixD1 Y, double[] gamma, int i)
    Computes the householder vector that is used to create reflector for the column.
    static boolean
    computeHouseHolderRow(int blockLength, DSubmatrixD1 Y, double[] gamma, int i)
    Computes the householder vector from the specified row
    static double
    computeTauAndDivideCol(int blockLength, DSubmatrixD1 Y, int col, double max)
    From the specified column of Y tau is computed and each element is divided by 'max'.
    static double
    computeTauAndDivideRow(int blockLength, DSubmatrixD1 Y, int row, int colStart, double max)
    From the specified row of Y tau is computed and each element is divided by 'max'.
    static void
    computeW_Column(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 W, @Nullable GrowArray<DGrowArray> workspace, double[] beta, int betaIndex)
    Computes W from the householder reflectors stored in the columns of the column block submatrix Y.
    static void
    computeY_t_V(int blockLength, DSubmatrixD1 Y, int col, double[] temp)
    Computes YTv(j).
    static void
    computeZ(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 W, int col, double[] temp, double beta)
    Computes the vector z and inserts it into 'W':

    z = - βj*(Vj + W*h)

    where h is a vector of length 'col' and was computed using computeY_t_V(int, org.ejml.data.DSubmatrixD1, int, double[]).
    static boolean
    decomposeQR_block_col(int blockLength, DSubmatrixD1 Y, double[] gamma)
    Performs a standard QR decomposition on the specified submatrix that is one block wide.
    static void
    divideElementsCol(int blockLength, DSubmatrixD1 Y, int col, double val)
    Divides the elements at the specified column by 'val'.
    static double
    findMaxCol(int blockLength, DSubmatrixD1 Y, int col)
    Finds the element in the column with the largest absolute value.
    static double
    findMaxRow(int blockLength, DSubmatrixD1 Y, int row, int colStart)
    Finds the element in the column with the largest absolute value.
    static void
    initializeW(int blockLength, DSubmatrixD1 W, DSubmatrixD1 Y, int widthB, double b)
    Sets W to its initial value using the first column of 'y' and the value of 'b':
    W = -βv

    where v = Y(:,0).
    static double
    innerProdCol(int blockLength, DSubmatrixD1 A, int colA, int widthA, int colB, int widthB)
    Computes the inner product of column vector 'colA' against column vector 'colB' while taking account leading zeros and one.

    ret = aT*b
    static double
    innerProdRow(int blockLength, DSubmatrixD1 A, int rowA, DSubmatrixD1 B, int rowB, int zeroOffset)
    Computes the inner product of row vector 'rowA' against row vector 'rowB' while taking account leading zeros and one.

    ret = aT*b
    static void
    multAdd_zeros(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 B, DSubmatrixD1 C)
    Special multiplication that takes in account the zeros and one in Y, which is the matrix that stores the householder vectors.
    static void
    multBlockAdd_zerosone(double[] dataA, double[] dataB, double[] dataC, int indexA, int indexB, int indexC, int heightA, int widthA, int widthC)
    Inner block mult add operation that takes in account the zeros and on in dataA, which is the top part of the Y block vector that has the householder vectors.

    C = C + A * B
    static void
    Performs a matrix multiplication on the block aligned submatrices.
    protected static void
    multTransABlockSet_lowerTriag(double[] dataA, double[] dataB, double[] dataC, int indexA, int indexB, int indexC, int heightA, int widthA, int widthC)
    Performs a matrix multiplication on an single inner block where A is assumed to be lower triangular with diagonal elements equal to 1.

    C = A^T * B
    static void
    rank1UpdateMultL_LeftCol(int blockLength, DSubmatrixD1 A, int row, double gamma, int zeroOffset)
    Applies a householder reflector stored in row 'row' to the left column block.
    static void
    rank1UpdateMultL_Row(int blockLength, DSubmatrixD1 A, int row, int colStart, double gamma)
    Applies a householder reflector stored in row 'row' to the remainder of the row in the block after it.
    static void
    rank1UpdateMultR_Col(int blockLength, DSubmatrixD1 A, int col, double gamma)
    Applies a householder reflector stored in column 'col' to the remainder of the columns in the block after it.
    static void
    rank1UpdateMultR_TopRow(int blockLength, DSubmatrixD1 A, int col, double gamma)
    Applies a householder reflector stored in column 'col' to the top block row (excluding the first column) of A.
    static void
    scale_row(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 W, int row, int zeroOffset, double val)
    Scales the elements in the specified row starting at element colStart by 'val'.
    W = val*Y Takes in account zeros and leading one automatically.

    Methods inherited from class java.lang.Object

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

    • BlockHouseHolder_DDRB

      public BlockHouseHolder_DDRB()
  • Method Details

    • decomposeQR_block_col

      public static boolean decomposeQR_block_col(int blockLength, DSubmatrixD1 Y, double[] gamma)
      Performs a standard QR decomposition on the specified submatrix that is one block wide.
    • computeHouseHolderCol

      public static boolean computeHouseHolderCol(int blockLength, DSubmatrixD1 Y, double[] gamma, int i)

      Computes the householder vector that is used to create reflector for the column. The results are stored in the original matrix.

      The householder vector 'u' is computed as follows:

      u(1) = 1
      u(i) = x(i)/(τ + x(1))

      The first element is implicitly assumed to be one and not written.
      Returns:
      If there was any problems or not. true = no problem.
    • computeHouseHolderRow

      public static boolean computeHouseHolderRow(int blockLength, DSubmatrixD1 Y, double[] gamma, int i)

      Computes the householder vector from the specified row

      The householder vector 'u' is computed as follows:

      u(1) = 1
      u(i) = x(i)/(τ + x(1))

      The first element is implicitly assumed to be one and not written.
      Returns:
      If there was any problems or not. true = no problem.
    • rank1UpdateMultR_Col

      public static void rank1UpdateMultR_Col(int blockLength, DSubmatrixD1 A, int col, double gamma)

      Applies a householder reflector stored in column 'col' to the remainder of the columns in the block after it. Takes in account leading zeros and one.

      A = (I - γ*u*uT)*A

      Parameters:
      A - submatrix that is at most one block wide and aligned along inner blocks
      col - The column in A containing 'u'
    • rank1UpdateMultR_TopRow

      public static void rank1UpdateMultR_TopRow(int blockLength, DSubmatrixD1 A, int col, double gamma)

      Applies a householder reflector stored in column 'col' to the top block row (excluding the first column) of A. Takes in account leading zeros and one.

      A = (I - γ*u*uT)*A

      Parameters:
      A - submatrix that is at most one block wide and aligned along inner blocks
      col - The column in A containing 'u'
    • rank1UpdateMultL_Row

      public static void rank1UpdateMultL_Row(int blockLength, DSubmatrixD1 A, int row, int colStart, double gamma)

      Applies a householder reflector stored in row 'row' to the remainder of the row in the block after it. Takes in account leading zeros and one.

      A = A*(I - γ*u*uT)

      Parameters:
      A - submatrix that is block aligned
      row - The row in A containing 'u'
      colStart - First index in 'u' that the reflector starts at
    • rank1UpdateMultL_LeftCol

      public static void rank1UpdateMultL_LeftCol(int blockLength, DSubmatrixD1 A, int row, double gamma, int zeroOffset)

      Applies a householder reflector stored in row 'row' to the left column block. Takes in account leading zeros and one.

      A = A*(I - γ*u*uT)

      Parameters:
      A - submatrix that is block aligned
      row - The row in A containing 'u'
      zeroOffset - How far off the diagonal is the first element in 'u'
    • innerProdCol

      public static double innerProdCol(int blockLength, DSubmatrixD1 A, int colA, int widthA, int colB, int widthB)

      Computes the inner product of column vector 'colA' against column vector 'colB' while taking account leading zeros and one.

      ret = aT*b

      Column A is assumed to be a householder vector. Element at 'colA' is one and previous ones are zero.

      Parameters:
      A - block aligned submatrix.
      colA - Column inside the block of first column vector.
      widthA - how wide the column block that colA is inside of.
      colB - Column inside the block of second column vector.
      widthB - how wide the column block that colB is inside of.
      Returns:
      dot product of the two vectors.
    • innerProdRow

      public static double innerProdRow(int blockLength, DSubmatrixD1 A, int rowA, DSubmatrixD1 B, int rowB, int zeroOffset)

      Computes the inner product of row vector 'rowA' against row vector 'rowB' while taking account leading zeros and one.

      ret = aT*b

      Row A is assumed to be a householder vector. Element at 'colStartA' is one and previous elements are zero.

      Parameters:
      A - block aligned submatrix.
      rowA - Row index inside the sub-matrix of first row vector has zeros and ones..
      rowB - Row index inside the sub-matrix of second row vector.
      Returns:
      dot product of the two vectors.
    • add_row

      public static void add_row(int blockLength, DSubmatrixD1 A, int rowA, double alpha, DSubmatrixD1 B, int rowB, double beta, DSubmatrixD1 C, int rowC, int zeroOffset, int end)
    • divideElementsCol

      public static void divideElementsCol(int blockLength, DSubmatrixD1 Y, int col, double val)
      Divides the elements at the specified column by 'val'. Takes in account leading zeros and one.
    • scale_row

      public static void scale_row(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 W, int row, int zeroOffset, double val)
      Scales the elements in the specified row starting at element colStart by 'val'.
      W = val*Y Takes in account zeros and leading one automatically.
      Parameters:
      zeroOffset - How far off the diagonal is the first element in the vector.
    • computeTauAndDivideCol

      public static double computeTauAndDivideCol(int blockLength, DSubmatrixD1 Y, int col, double max)

      From the specified column of Y tau is computed and each element is divided by 'max'. See code below:

       for i=col:Y.numRows
         Y[i][col] = u[i][col] / max
         tau = tau + u[i][col]*u[i][col]
       end
       tau = sqrt(tau)
       if( Y[col][col] < 0 )
          tau = -tau;
       
    • computeTauAndDivideRow

      public static double computeTauAndDivideRow(int blockLength, DSubmatrixD1 Y, int row, int colStart, double max)

      From the specified row of Y tau is computed and each element is divided by 'max'. See code below:

       for j=row:Y.numCols
         Y[row][j] = u[row][j] / max
         tau = tau + u[row][j]*u[row][j]
       end
       tau = sqrt(tau)
       if( Y[row][row] < 0 )
          tau = -tau;
       
      Parameters:
      row - Which row in the block will be processed
      colStart - The first column that computation of tau will start at
      max - used to normalize and prevent buffer over flow
    • findMaxCol

      public static double findMaxCol(int blockLength, DSubmatrixD1 Y, int col)
      Finds the element in the column with the largest absolute value. The offset from zero is automatically taken in account based on the column.
    • findMaxRow

      public static double findMaxRow(int blockLength, DSubmatrixD1 Y, int row, int colStart)
      Finds the element in the column with the largest absolute value. The offset from zero is automatically taken in account based on the column.
    • computeW_Column

      public static void computeW_Column(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 W, @Nullable @Nullable GrowArray<DGrowArray> workspace, double[] beta, int betaIndex)

      Computes W from the householder reflectors stored in the columns of the column block submatrix Y.

      Y = v(1)
      W = -β1v(1)
      for j=2:r
        z = -β(I +WYT)v(j)
        W = [W z]
        Y = [Y v(j)]
      end

      where v(.) are the house holder vectors, and r is the block length. Note that Y already contains the householder vectors so it does not need to be modified.

      Y and W are assumed to have the same number of rows and columns.

      Parameters:
      Y - Input matrix containing householder vectors. Not modified.
      W - Resulting W matrix. Modified.
      workspace - (Optional) Storage for workspace. Can be null.
      beta - Beta's for householder vectors.
      betaIndex - Index of first relevant beta.
    • initializeW

      public static void initializeW(int blockLength, DSubmatrixD1 W, DSubmatrixD1 Y, int widthB, double b)

      Sets W to its initial value using the first column of 'y' and the value of 'b':
      W = -βv

      where v = Y(:,0).

      Parameters:
      blockLength - size of the inner block
      W - Submatrix being initialized.
      Y - Contains householder vector
      widthB - How wide the W block matrix is.
      b - beta
    • computeZ

      public static void computeZ(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 W, int col, double[] temp, double beta)
      Computes the vector z and inserts it into 'W':

      z = - βj*(Vj + W*h)

      where h is a vector of length 'col' and was computed using computeY_t_V(int, org.ejml.data.DSubmatrixD1, int, double[]). V is a column in the Y matrix. Z is a column in the W matrix. Both Z and V are column 'col'.
    • computeY_t_V

      public static void computeY_t_V(int blockLength, DSubmatrixD1 Y, int col, double[] temp)
      Computes YTv(j). Where Y are the columns before 'col' and v is the column at 'col'. The zeros and ones are taken in account. The solution is a vector with 'col' elements. width of Y must be along the block of original matrix A
      Parameters:
      temp - Temporary storage of least length 'col'
    • multAdd_zeros

      public static void multAdd_zeros(int blockLength, DSubmatrixD1 Y, DSubmatrixD1 B, DSubmatrixD1 C)
      Special multiplication that takes in account the zeros and one in Y, which is the matrix that stores the householder vectors.
    • multBlockAdd_zerosone

      public static void multBlockAdd_zerosone(double[] dataA, double[] dataB, double[] dataC, int indexA, int indexB, int indexC, int heightA, int widthA, int widthC)

      Inner block mult add operation that takes in account the zeros and on in dataA, which is the top part of the Y block vector that has the householder vectors.

      C = C + A * B

    • multTransA_vecCol

      public static void multTransA_vecCol(int blockLength, DSubmatrixD1 A, DSubmatrixD1 B, DSubmatrixD1 C)

      Performs a matrix multiplication on the block aligned submatrices. A is assumed to be block column vector that is lower triangular with diagonal elements set to 1.

      C = A^T * B

    • multTransABlockSet_lowerTriag

      protected static void multTransABlockSet_lowerTriag(double[] dataA, double[] dataB, double[] dataC, int indexA, int indexB, int indexC, int heightA, int widthA, int widthC)
      Performs a matrix multiplication on an single inner block where A is assumed to be lower triangular with diagonal elements equal to 1.

      C = A^T * B