dev.nm.algebra.linear.matrix.doubles.factorization.diagonalization

Class BiDiagonalizationByHouseholder

java.lang.Object

dev.nm.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 \(U_{1}'\) 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_{1}\). (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_{1} \cdot \ldots \cdot U_{n})' \cdot A \cdot (V_{1} \cdot \ldots \cdot 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

Constructors

Constructor and Description
BiDiagonalizationByHouseholder(Matrix A) Runs the Householder bi-diagonalization for a tall matrix.

Method Summary

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^{'} = U_{k} \cdot \ldots \cdot U_{1}\), k = A.nCols() (or k = A.nCols() - 1 for square A).
Matrix	V() Gets V, where \(V^{'} = V_{k} \cdot \ldots \cdot V_{1}\), k = A.nCols() - 2.

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

See Also:

"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^{'} = U_{k} \cdot \ldots \cdot U_{1}\), 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 \(U_{i}\)'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^{'} = V_{k} \cdot \ldots \cdot V_{1}\), 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.

Specified by:

V in interface BiDiagonalization

Returns:

the V matrix