com.numericalmethod.suanshu.matrix.doubles.operation

Class Householder

java.lang.Object

com.numericalmethod.suanshu.matrix.doubles.operation.Householder

All Implemented Interfaces:

java.io.Serializable

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

A Householder transformation in the 3-dimensional space is the reflection of a vector in the plane. The plane, containing the origin, is uniquely defined by a unit vector, called the generator, orthogonal to the plane. The reflection Hx can be computed without explicitly expanding H.

 H = I - 2vv'
 Hx = (I - 2vv')x = Ix - 2vv'x = x - 2v<v,x>, where x is a column vector
 yH = (H'y')' = (Hy')', where y is a row vector
 

When H is applied to a set of column vectors, it transforms each vector individually, as in block matrix multiplication.

 H * A = H * [A1 A2 ... An] = [H * A1 H * A2 ... H * An]
 

When H is applied to a set of row vectors, it transforms each vector individually, as in block matrix multiplication. \[ AH = \begin{bmatrix} A_1H\\ A_2H\\ A_3H\\ A_4H\\ A_5H \end{bmatrix} \]

See Also:

• Wikipedia: Householder transformation
• Wikipedia: Householder operator

, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Householder.Context This is the context information about a Householder transformation.

Constructor Summary

Constructors

Constructor and Description
Householder(Vector generator) Construct a Householder matrix from the vector that defines the hyperplane orthogonal to the vector.

Method Summary

Modifier and Type	Method and Description
Vector	generator() Get the Householder generating vector.
static Householder.Context	getContext(Vector x) Generate the context information from a generating vector x.
Matrix	H() Get the Householder matrix H = I - 2 * v * v'.
static Matrix	product(Householder[] Hs, int from, int to) Compute Q from Householder matrices {Qi}.
static Matrix	product(Householder[] Hs, int from, int to, int nRows, int nCols) Compute Q from Householder matrices {Qi}.
Matrix	reflect(Matrix A) Apply the Householder matrix, H, to a matrix (a set of column vectors), A.
Vector	reflect(Vector x) Apply the Householder matrix, H, to a column vector, x.
Matrix	reflectRows(Matrix A) Apply the Householder matrix, H, to a matrix (a set of row vectors), A.

Methods inherited from class java.lang.Object

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

Constructor Detail

Householder

public Householder(Vector generator)

Construct a Householder matrix from the vector that defines the hyperplane orthogonal to the vector. If the generator is a 0-vector, the Householder matrix is the identity matrix.

Parameters:

generator - the hyperplane defining vector

Method Detail

generator

public Vector generator()

Get the Householder generating vector.

Returns:

the Householder generating vector

reflect

public Vector reflect(Vector x)

Apply the Householder matrix, H, to a column vector, x.

 Hx = x - 2 * <v,x> * v
 

Parameters:

x - a vector

Returns:

Hx

reflect

public Matrix reflect(Matrix A)

Apply the Householder matrix, H, to a matrix (a set of column vectors), A.

 H * A = [H * A1 H * A2 ... H * An]
 

Parameters:

A - a matrix

Returns:

H * A

reflectRows

public Matrix reflectRows(Matrix A)

Apply the Householder matrix, H, to a matrix (a set of row vectors), A. \[ AH = \begin{bmatrix} A_1H\\ A_2H\\ A_3H\\ A_4H\\ A_5H \end{bmatrix} \]

Parameters:

A - a matrix

Returns:

A * H

H

public Matrix H()

Get the Householder matrix H = I - 2 * v * v'. To compute H *v, do not use this method. Instead use reflect(Vector).

Returns:

the Householder matrix

product

public static Matrix product(Householder[] Hs,
                             int from,
                             int to,
                             int nRows,
                             int nCols)

Compute Q from Householder matrices {Q_i}.

 Q = Q1 * Q2 * ... * Qn * I
 

The identity matrix, I, may have more rows than columns. The bottom rows are padded with zeros.

This implementation use an efficient way to compute Q, i.e., by applying Q_i's repeatedly on an identity matrix.

Parameters:

Hs - an array of Householders

from - the beginning index of H's; Q₁ is Q_from

to - the ending index of H's; Q_n is Q_to

nRows - the number of rows of I

nCols - the number of columns of I

Returns:

the product of an array of Householder matrices, from Hs[from] to Hs[to]

product

public static Matrix product(Householder[] Hs,
                             int from,
                             int to)

Compute Q from Householder matrices {Q_i}.

 Q = Q1 * Q2 * ... * Qn * I
 

This implementation use an efficient way to compute Q, i.e., by applying Q_i's repeatedly on an identity matrix.

Parameters:

Hs - an array of Householders

from - the beginning index of H's; Q₁ is Q_from

to - the ending index of H's; Q_n is Q_to

Returns:

the product of an array of Householder matrices, from Hs[from] to Hs[to]

getContext

public static Householder.Context getContext(Vector x)

Generate the context information from a generating vector x. Given a vector x, return a vector generator, such that

 Hx = ±||x|| * e1
 

That is,

 H.reflect(x) == new Vector(new double[]{±x.norm(), 0, ...})
 

Parameters:

x - a vector

Returns:

the context information for a Householder transformation

See Also:

"G. W. Steward, "Algorithm 1.1," Matrix Algorithms, Volume 1"