com.numericalmethod.suanshu.matrix.doubles.factorization.qr

Class HouseholderReflection

java.lang.Object

com.numericalmethod.suanshu.matrix.doubles.factorization.qr.HouseholderReflection

All Implemented Interfaces:

QRDecomposition, java.io.Serializable

public class HouseholderReflection
extends java.lang.Object
implements QRDecomposition

Successive Householder reflections gradually transform a matrix A to the upper triangular form. For example, the first step is to multiply A with a Householder matrix Q₁ so that matrix Q₁ * A has zeros in the left column (except for the first row). That is, \[ Q_1 \times A = \begin{bmatrix} a_1 & * & ... & * \\ 0 & & & \\ ... & & & \\ ... & & A' & \\ ... & & & \\ 0 & & & \end{bmatrix} \] At the end,\(Q_n \times ... \times Q_1 \times A = R\) where R is upper triangular.

Householder reflection has a better numerical stability than the Gram-Schmidt process.

See Also:

Wikipedia: Using Householder reflections, Serialized Form

Constructor Summary

Constructors

Constructor and Description
HouseholderReflection(Matrix A) Run the Householder reflection process to orthogonalize a matrix.
HouseholderReflection(Matrix A, double epsilon) Run the Householder reflection process to orthogonalize a matrix.

Method Summary

Modifier and Type	Method and Description
PermutationMatrix	P() Get P, the pivoting matrix in the QR decomposition.
Matrix	Q() Get the Q matrix in the QR decomposition.
UpperTriangularMatrix	R() Get the upper triangular matrix R in the QR decomposition, A = QR.
int	rank() This implementation computes the rank by counting the number of non-zero rows in R.
Matrix	squareQ() Get the square Q matrix.
Matrix	tallR() Get the tall R matrix.

Methods inherited from class java.lang.Object

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

Constructor Detail

HouseholderReflection

public HouseholderReflection(Matrix A,
                             double epsilon)

Run the Householder reflection process to orthogonalize a matrix.

Parameters:

A - a matrix, where the number of rows ≥ the number of columns

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

Throws:

java.lang.IllegalArgumentException - if the number of rows < the number of columns

HouseholderReflection

public HouseholderReflection(Matrix A)

Run the Householder reflection process to orthogonalize a matrix.

Parameters:

A - a matrix, where the number of rows ≥ the number of columns

Method Detail

Q

public Matrix Q()

Get the Q matrix in the QR decomposition. The dimension of Q is nRows x nCols. \[ \begin{array}{lcl} Q_n \times ... \times Q_3 \times Q_2 \times Q_1 \times A = R \\ A = [Q_n \times ... \times Q_3 \times Q_2 \times Q_1]^{-1} \times R \\ = [Q_1^{-1} \times Q_2^{-1} \times ... \times Q_n^{-1}] \times R \\ = [Q_1 \times Q_2 \times ... \times Q_n] \times R \\ Q = Q_1 \times Q_2 \times ... \times Q_n \end{array} \] \(Q_1^{-1} = Q_1\) , by the unitary property of Householder matrix

This implementation does not compute Q by explicitly doing this multiplication. Instead, we improve the performance by applying Q_i's repeatedly on an identity matrix.

Specified by:

Q in interface QRDecomposition

Returns:

Q

R

public UpperTriangularMatrix R()

Description copied from interface: QRDecomposition

Get the upper triangular matrix R in the QR decomposition, A = QR. The dimension of R is n x n, a square matrix.

Specified by:

R in interface QRDecomposition

Returns:

R

P

public PermutationMatrix P()

Get P, the pivoting matrix in the QR decomposition. Householder process does not need pivoting. Hence, P is always an identity matrix.

Specified by:

P in interface QRDecomposition

Returns:

an identity matrix

rank

public int rank()

This implementation computes the rank by counting the number of non-zero rows in R.

Note that Q may have more columns than the rank. The user should interpret the result with caution.

Specified by:

rank in interface QRDecomposition

Returns:

the rank

squareQ

public Matrix squareQ()

Description copied from interface: QRDecomposition

Get the square Q matrix. This is an arbitrary orthogonal completion of the Q matrix in the QR decomposition. The dimension is m x m (square). We have A = sqQ * tallR.

Specified by:

squareQ in interface QRDecomposition

Returns:

the square Q matrix

tallR

public Matrix tallR()

Description copied from interface: QRDecomposition

Get the tall R matrix. This is completed by binding zero rows beneath the square upper triangular matrix R in the QR decomposition. The dimension is m x n. It may not be square. We have A = sqQ * tallR.

Specified by:

tallR in interface QRDecomposition

Returns:

the tall R matrix