Class GramSchmidt
- java.lang.Object
-
- dev.nm.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 theHouseholder reflection
, 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
-
-
Constructor Summary
Constructors Constructor 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 Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
Constructor Detail
-
GramSchmidt
public GramSchmidt(Matrix A, boolean pad0Cols, double epsilon)
Run the Gram-Schmidt process to orthogonalize a matrix.- Parameters:
A
- a matrixpad0Cols
- 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 interfaceQRDecomposition
- 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 interfaceQRDecomposition
- Returns:
- R
-
P
public PermutationMatrix P()
Description copied from interface:QRDecomposition
Get P, the pivoting matrix in the QR decomposition.- Specified by:
P
in interfaceQRDecomposition
- 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 interfaceQRDecomposition
- 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- the columns of I - P = I - Q * Q', or
- 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.
- Specified by:
squareQ
in interfaceQRDecomposition
- 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 interfaceQRDecomposition
- Returns:
- the tall R matrix
-
-