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

Class GramSchmidt

java.lang.Object

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

All Implemented Interfaces:

QRDecomposition, java.io.Serializable

public class GramSchmidt
extends java.lang.Object
implements QRDecomposition

The Gram–Schmidt process is a method for orthogonalizing a set of vectors in an inner product space. It does so by iteratively computing the vector orthogonal to the subspace spanned by the previously found orthogonal vectors. An orthogonal vector is the difference between a column vector and its projection on the subspace.

There is the problem of "loss of orthogonality" during the process. In general, the bigger the matrix is, e.g., dimension = 3500x3500, the less precise the result is. The vectors in Q may not be as orthogonal. This implementation uses a numerically stable Gram–Schmidt process with twice re-orthogonalization to alleviate the problem of rounding errors.

Numerical determination of rank requires a criterion to decide how small a value should be treated as zero. This is a practical choice which depends on both the matrix and the application. For instance, for a matrix with a big first eigenvector, we should accordingly decrease the precision to compute the rank.

While the result for the orthogonal basis may match those of the Householder Reflection HouseholderReflection, the result for the orthogonal complement may differ because the kernel basis is not unique.

See Also:

• "Luc Giraud, Julien Langou, Miroslav Rozloznik, "On the loss of orthogonality in the Gram-Schmidt orthogonalization process," Computers & Mathematics with Applications, Volume 50, Issue 7, October 2005, p. 1069-1075. Numerical Methods and Computational Mechanics."
• "Gene H. Golub, Charles F. Van Loan, Matrix Computations (Johns Hopkins Studies in Mathematical Sciences)(3rd Edition)(Paperback)."
• Wikipedia: Gram–Schmidt process

, Serialized Form

Constructor Summary

Constructors

Constructor and Description
GramSchmidt(Matrix A) Run the Gram-Schmidt process to orthogonalize a matrix.
GramSchmidt(Matrix A, boolean pad0Cols, double epsilon) Run the Gram-Schmidt 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 orthogonal Q matrix in the QR decomposition, A = QR.
UpperTriangularMatrix	R() Get the upper triangular matrix R in the QR decomposition, A = QR.
int	rank() Get the numerical rank of A as computed by the QR decomposition.
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

GramSchmidt

public GramSchmidt(Matrix A,
                   boolean pad0Cols,
                   double epsilon)

Run the Gram-Schmidt process to orthogonalize a matrix.

Parameters:

A - a matrix

pad0Cols - when a column is linearly dependent on the previous columns, there is no orthogonal vector. We pad the basis with a 0-vector.

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

GramSchmidt

public GramSchmidt(Matrix A)

Run the Gram-Schmidt process to orthogonalize a matrix.

Parameters:

A - a matrix

Method Detail

Q

public Matrix Q()

Description copied from interface: QRDecomposition

Get the orthogonal Q matrix in the QR decomposition, A = QR. The dimension of Q is m x n, the same as A, the matrix to be orthogonalized.

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()

Description copied from interface: QRDecomposition

Get P, the pivoting matrix in the QR decomposition.

Specified by:

P in interface QRDecomposition

Returns:

P

rank

public int rank()

Description copied from interface: QRDecomposition

Get the numerical rank of A as computed by the QR decomposition. Numerical determination of rank requires a criterion to decide when a value should be treated as zero, hence a precision parameter. This is a practical choice which depends on both the matrix and the application. For instance, for a matrix with a big first eigenvector, we should accordingly decrease the precision to compute the rank.

Specified by:

rank in interface QRDecomposition

Returns:

the rank of A

squareQ

public Matrix squareQ()

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. This implementation extends Q by appending A's orthogonal complement. Suppose Q has the orthogonal basis for a subspace A. To compute the orthogonal complement of A, we apply the Gram-Schmidt procedure to either

1. the columns of I - P = I - Q * Q', or
2. the spanning set \(\left \{ u_1, u_2, ..., u_k, e_1, e_2, ..., e_n \right \}\) and keeping only the first n elements of the resulting basis of R_n. The last n-k elements are the basis for the orthogonal complement. k is the rank.

We implemented the second option.

Specified by:

squareQ in interface QRDecomposition

Returns:

the spanning set of both the orthogonal basis of A and the orthogonal complement

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