# SuanShu, a Java numerical and statistical library

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

## Class BiDiagonalizationByHouseholder

• java.lang.Object
• com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.diagonalization.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 Summary

Constructors
Constructor and Description
BiDiagonalizationByHouseholder(Matrix A)
Runs the Householder bi-diagonalization for a tall matrix.
• ### Method Summary

All Methods
Modifier and Type Method and Description
BidiagonalMatrix B()
Gets B, which is the square upper part of U.t().multiply(A).multiply(V).
Matrix U()
Gets U, where U' = Uk * ...
Matrix V()
Gets V, where V' = Vk * ...
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### 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
"G. H. Golub, C. F. van Loan, "Algorithm 5.4.2," Matrix Computations, 3rd edition."
• ### 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