com.numericalmethod.suanshu.matrix.doubles.factorization.diagonalization
Class BiDiagonalization

java.lang.Object
  com.numericalmethod.suanshu.matrix.doubles.factorization.diagonalization.BiDiagonalization

public class BiDiagonalization
extends java.lang.Object

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 U₁' 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 V₁. (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, (U₁ * ... * U_n)' * A * (V₁ * ... * V_n) = 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

BiDiagonalization(Matrix A)
Run the Householder bi-diagonalization for a tall matrix.

Method Summary

BidiagonalMatrix	B() Get B, which is the square upper part of U.t().multiply(A).multiply(V).
Matrix	U() Get U, where U' = Uk * ...
Matrix	V() Get V, where V' = Vk * ...

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BiDiagonalization

public BiDiagonalization(Matrix A)

Run the Householder bi-diagonalization for a tall matrix.

Parameters:

A - a tall matrix

Throws:

java.lang.IllegalArgumentException - if A is not tall

See Also:

"G. H. Golub, C. F. van Loan, "Algorithm 5.4.2," Matrix Computations, 3rd edition."

Method Detail

U

public Matrix U()

Get U, where U^' = U_k * ... * U₁, k = A.nCols(). The dimension of U is m x m.

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

Returns:

the U matrix

V

public Matrix V()

Get V, where V^' = V_k * ... * V₁, 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 V_i's repeatedly on an identity matrix. We take the transpose afterward.

Returns:

the V matrix

B

public BidiagonalMatrix B()

Get B, which is the square upper part of U.t().multiply(A).multiply(V). The dimension of B is n x n.

Returns:

B