# SuanShu, a Java numerical and statistical library

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

## Class GramSchmidt

• java.lang.Object
• com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.qr.GramSchmidt
• All Implemented Interfaces:
QRDecomposition

public class GramSchmidt
extends 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, the result for the orthogonal complement may differ because the kernel basis is not unique.

• "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
• ### 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

All Methods
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,
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 Rn. 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