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

Class HessenbergDecomposition

java.lang.Object

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

All Implemented Interfaces:

java.io.Serializable

public class HessenbergDecomposition
extends java.lang.Object
implements java.io.Serializable

Given a square matrix A, we find Q such that Q' * A * Q = H where H is a Hessenberg matrix. This implementation uses Householder reflection to repeatedly zero out the elements below the sub-diagonal. For example, the first step is to left multiply A by a Householder matrix Q₁ so that matrix Q₁ * A has zeros in the left column (except for the first two rows). That is (Q's are Hermitian.), \[ Q_1 \times A = Q_1' \times A = \begin{bmatrix} a_{11} & * & ... & * \\ a_{21} & & & \\ 0 & & & \\ ... & &A ' & \\ ... & & & \\ 0 & & & \end{bmatrix} \] Then, we right multiply A by Q₁. We have \[ Q_1' \times A \times Q_1 = \begin{bmatrix} a_{11} & ? & ... & ? \\ a_{21} & & & \\ 0 & & & \\ ... & & A'' & \\ ... & & & \\ 0 & & & \end{bmatrix} \] At the end, we have a Hessenberg H such that \[ (Q_n' \times ... \times Q_1') \times A \times (Q_1 \times ... \times Q_n) = H \] We have \[ Q = (Q_1 \times ... \times Q_n) \] This transformation always succeeds.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
HessenbergDecomposition(Matrix A) Run the Hessenberg decomposition for a square matrix.

Method Summary

Modifier and Type	Method and Description
Matrix	H() Get the H matrix.
Matrix	Q() Get the Q matrix, where \[ Q = (Q_1 \times ...

Methods inherited from class java.lang.Object

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

Constructor Detail

HessenbergDecomposition

public HessenbergDecomposition(Matrix A)

Run the Hessenberg decomposition for a square matrix. This decomposition does not require a precision parameter, though checking the result will need an epsilon.

Parameters:

A - a square matrix

Throws:

java.lang.IllegalArgumentException - if A is not square

See Also:

Hessenberg.isHessenberg(com.numericalmethod.suanshu.matrix.doubles.Matrix, double), "G. H. Golub, C. F. van Loan, "Algorithm 7.4.2," Matrix Computations, 3rd edition."

Method Detail

Q

public Matrix Q()

Get the Q matrix, where \[ Q = (Q_1 \times ... \times Q_n) \] n = dim - 2.

To compute Q, instead of explicitly doing this multiplication, we can improve the performance by applying the Q_i's repeatedly on an identity matrix.

Returns:

the Q matrix in the QR decomposition

H

public Matrix H()

Get the H matrix.

Returns:

H