maspack.matrix

Class QRDecomposition

java.lang.Object

maspack.matrix.QRDecomposition

public class QRDecomposition
extends java.lang.Object

Constructs the QR decomposition of a matrix. This takes the form
M = Q R
where M is the original matrix, Q is orthogonal, and R is upper-triangular. Nominally, if M has a size m X n, then if m >= n, R is square with size n and Q is m X n. Otherwise, if m < n, Q is square with size m and R has size m X n.

Note that if m > n, then R and M can actually have sizes p X n and m X p, with n <= p <= m, with the additional rows of R set to zero and the additional columns of Q formed by completing the orthogonal basis.

Once constructed, a QR decomposition can be used to perform various computations related to M, such as solving equations (in particular, determining least-squares solutions), computing the determinant, or estimating the condition number.

Providing a separate class for the QR decomposition allows an application to perform such decompositions repeatedly without having to reallocate temporary storage space.

Constructor Summary

Constructors

Constructor and Description
QRDecomposition() Creates an uninitialized QRDecomposition.
QRDecomposition(Matrix M) Creates a QRDecomposition for the Matrix specified by M.

Method Summary

Modifier and Type	Method and Description
double	conditionEstimate() Estimates the condition number of the triangular matrix R associated with this decomposition.
double	determinant() Returns the determinant of the (square) upper partition of R, times the determinant of Q.
void	factor(Matrix M) Peforms a QR decomposition on the Matrix M.
void	factorInPlace(MatrixNd M) Performs a QR decomposition on the Matrix M, placing the result in M and using M as the storage for subsequent solve operations.
void	factorWithPivoting(Matrix M) Peforms a QR decomposition, with pivoting, on the Matrix M.
void	get(MatrixNd Q, MatrixNd R) Gets the Q and R matrices associated with this QR decomposition.
void	get(MatrixNd Q, MatrixNd R, int[] cperm) Gets the Q and R matrices, and the column permutation, associated with this QR decomposition.
boolean	inverse(DenseMatrix X) Computes the inverse of the original matrix M associated with this decomposition, and places the result in X.
boolean	leftSolveR(DenseMatrix X, Matrix B) Computes a left solution to the linear equation X R = B where R is the upper triangular matrix associated with this decomposition, and X and B are matrices.
boolean	leftSolveR(Vector x, Vector b) Computes a left solution to the linear equation x R = b where R is the upper triangular matrix associated with this decomposition, and x and b are vectors.
static void	main(java.lang.String[] args)
void	postMulQ(MatrixNd MR, MatrixNd M1) Computes
void	postMulQTranspose(MatrixNd MR, MatrixNd M1) Computes
void	preMulQ(MatrixNd MR, MatrixNd M1) Computes
void	preMulQTranspose(MatrixNd MR, MatrixNd M1) Computes
int	rank(double tol)
boolean	solve(DenseMatrix X, Matrix B) Computes a least-squares solution to the linear equation M X = B where M is the original matrix associated with this decomposition, and X and B are matrices.
boolean	solve(Vector x, Vector b) Computes a least-squares solution to the linear equation M x = b where M is the original matrix associated with this decomposition, and x and b are vectors.
boolean	solveR(DenseMatrix X, Matrix B) Computes a solution to the linear equation R X = B where R is the upper triangular matrix associated with this decomposition, and X and B are matrices.
boolean	solveR(Vector x, Vector b) Computes a solution to the linear equation R x = b where R is the upper triangular matrix associated with this decomposition, and x and b are vectors.

Methods inherited from class java.lang.Object

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

Constructor Detail

QRDecomposition

public QRDecomposition(Matrix M)

Creates a QRDecomposition for the Matrix specified by M.

Parameters:

M - matrix to perform the QR decomposition on

QRDecomposition

public QRDecomposition()

Creates an uninitialized QRDecomposition.

Method Detail

factor

public void factor(Matrix M)

Peforms a QR decomposition on the Matrix M.

Parameters:

M - matrix to perform the QR decomposition on

factorInPlace

public void factorInPlace(MatrixNd M)

Performs a QR decomposition on the Matrix M, placing the result in M and using M as the storage for subsequent solve operations. Subsequent modification of M will invalidate the decomposition.

factorWithPivoting

public void factorWithPivoting(Matrix M)

Peforms a QR decomposition, with pivoting, on the Matrix M. Adapted from Algorithm 5.4.1, Golub and van Loan, second edition.

Parameters:

M - matrix to perform the QR decomposition on

get

public void get(MatrixNd Q,
                MatrixNd R)
         throws ImproperStateException,
                ImproperSizeException

Gets the Q and R matrices associated with this QR decomposition. Each argument is optional; values will be returned into them if they are present. Details on the appropriate dimensions for Q and R are described in the documentation for get(Q,R,cperm).

Parameters:

Q - returns the orthogonal matrix

R - returns the upper triangular matrix.

Throws:

ImproperStateException - if this QRDecomposition is uninitialized

ImproperSizeException - if Q or R are not of the proper dimension and cannot be resized.

get

public void get(MatrixNd Q,
                MatrixNd R,
                int[] cperm)
         throws ImproperStateException,
                ImproperSizeException

Gets the Q and R matrices, and the column permutation, associated with this QR decomposition. The column permutation is the identity unless the decomposition was performed with factorWithPivoting. Each argument is optional; values will be returned into them if they are present. Q is an orthogonal matrix which can be m X p, where min(n,m) <= p <= m (and so must be square if m <= n). Extra columns of Q are formed by completing the original basis. R is an upper triangular matrix which can be q X n, where min(n,m) <= q <= m (and so must be m X n if m <= n). Extra rows of R are set to zero.

Parameters:

Q - returns the orthogonal matrix

R - returns the upper triangular matrix

cperm - returns the indices of the column permutation matrix P, such that j-th column of M P is given by column perm[j] of M.

Throws:

ImproperStateException - if this QRDecomposition is uninitialized

ImproperSizeException - if Q or R are not of the proper dimension and cannot be resized.

solve

public boolean solve(Vector x,
                     Vector b)
              throws ImproperStateException,
                     ImproperSizeException

Computes a least-squares solution to the linear equation
M x = b
where M is the original matrix associated with this decomposition, and x and b are vectors. The number of rows in M must equal or exceed the number of columns.

Parameters:

x - unknown vector to solve for

b - constant vector

Returns:

false if M does not have full column rank (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - if M has fewer rows than columns, if b does not have a size compatible with M, or if x does not have a size compatible with M and cannot be resized.

solve

public boolean solve(DenseMatrix X,
                     Matrix B)
              throws ImproperStateException,
                     ImproperSizeException

Computes a least-squares solution to the linear equation
M X = B
where M is the original matrix associated with this decomposition, and X and B are matrices. The number of rows in M must equal or exceed the number of columns.

Parameters:

X - unknown matrix to solve for

B - constant matrix

Returns:

false if M does not have full column rank (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - if M has fewer rows than columns, if B has a different number of rows than M, or if X has a different number of rows than M or a different number of columns than B and cannot be resized.

solveR

public boolean solveR(Vector x,
                      Vector b)
               throws ImproperStateException,
                      ImproperSizeException

Computes a solution to the linear equation
R x = b
where R is the upper triangular matrix associated with this decomposition, and x and b are vectors. Note that R is a square matrix with a size equal to the the number of columns in the original matrix M.

Parameters:

x - unknown vector to solve for

b - constant vector

Returns:

false if R is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - if b does not have a size compatible with R, or if x does not have a size compatible with R and cannot be resized.

solveR

public boolean solveR(DenseMatrix X,
                      Matrix B)
               throws ImproperStateException,
                      ImproperSizeException

Computes a solution to the linear equation
R X = B
where R is the upper triangular matrix associated with this decomposition, and X and B are matrices. Note that R is a square matrix with a size equal to the the number of columns in the original matrix M.

Parameters:

X - unknown matrix to solve for

B - constant matrix

Returns:

false if R is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - if the size of B is incompatible with R, or if the size of X is incompatible with R or B and X cannot be resized.

leftSolveR

public boolean leftSolveR(Vector x,
                          Vector b)
                   throws ImproperStateException,
                          ImproperSizeException

Computes a left solution to the linear equation
x R = b
where R is the upper triangular matrix associated with this decomposition, and x and b are vectors. Note that R is a square matrix with a size equal to the the number of columns in the original matrix M.

Parameters:

x - unknown vector to solve for

b - constant vector

Returns:

false if R is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - if b does not have a size compatible with R, or if x does not have a size compatible with R and cannot be resized.

leftSolveR

public boolean leftSolveR(DenseMatrix X,
                          Matrix B)
                   throws ImproperStateException,
                          ImproperSizeException

Computes a left solution to the linear equation
X R = B
where R is the upper triangular matrix associated with this decomposition, and X and B are matrices. Note that R is a square matrix with a size equal to the the number of columns in the original matrix M.

Parameters:

X - unknown matrix to solve for

B - constant matrix

Returns:

false if R is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - if the size of B is incompatible with R, or if the size of X is incompatible with R or B and X cannot be resized.

conditionEstimate

public double conditionEstimate()
                         throws ImproperStateException

Estimates the condition number of the triangular matrix R associated with this decomposition. The number of rows in the original matrix M should equal or exceed the number of columns. The algorithm for estimating the condition number is given in Section 3.5.4 of Golub and Van Loan, Matrix Computations (Second Edition).

Returns:

condition number estimate

Throws:

ImproperStateException - if this QRDecomposition is uninitialized

ImproperSizeException - if M has fewer rows than columns.

determinant

public double determinant()
                   throws ImproperStateException

Returns the determinant of the (square) upper partition of R, times the determinant of Q. This equals the determinant of the original matrix M in the case where M is square.

Returns:

determinant (or product of R diagonals)

Throws:

ImproperStateException - if this decomposition is uninitialized

inverse

public boolean inverse(DenseMatrix X)
                throws ImproperStateException

Computes the inverse of the original matrix M associated with this decomposition, and places the result in X. M must be square.

Parameters:

X - matrix in which the inverse is stored

Returns:

false if M is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - if M is not square, or if X does not have the same size as M and cannot be resized.

rank

public int rank(double tol)

preMulQ

public void preMulQ(MatrixNd MR,
                    MatrixNd M1)

Computes

   MR = Q M1
 

where Q is the full m X m orthogonal matrix associated with the decomposition. Before calling this method, the decomposition must be initialized with a factorization. In order to conform with Q, M1 must have m rows.

Parameters:

MR - result matrix

M1 - matrix to pre-multiply by Q

preMulQTranspose

public void preMulQTranspose(MatrixNd MR,
                             MatrixNd M1)

Computes

   MR = Q^T M1
 

where Q is the full m X m orthogonal matrix associated with the decomposition. Before calling this method, the decomposition must be initialized with a factorization. In order to conform with Q, M1 must have m rows.

Parameters:

MR - result matrix

M1 - matrix to pre-multiply by Q transpose

postMulQ

public void postMulQ(MatrixNd MR,
                     MatrixNd M1)

Computes

   MR = M1 Q
 

where Q is the full m X m orthogonal matrix associated with the decomposition. Before calling this method, the decomposition must be initialized with a factorization. In order to conform with Q, M1 must have m columns.

Parameters:

MR - result matrix

M1 - matrix to post-multiply by Q

postMulQTranspose

public void postMulQTranspose(MatrixNd MR,
                              MatrixNd M1)

Computes

   MR = M1 Q^T
 

where Q is the full m X m orthogonal matrix associated with the decomposition. Before calling this method, the decomposition must be initialized with a factorization. In order to conform with Q, M1 must have m columns.

Parameters:

MR - result matrix

M1 - matrix to post-multiply by Q transpose

main

public static void main(java.lang.String[] args)