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.

If the decomposition is performed with pivoting, using the method factorWithPivoting(maspack.matrix.Matrix), then it takes the form

 M P = Q R
 

where P is a permutation matrix.

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.
MatrixNd	getQ() Returns the Q matrix associated with this QR decomposition.
MatrixNd	getR() Returns the R matrix 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	leftSolve(DenseMatrix X, Matrix B) Computes a left solution to the linear equation x M = b where M is the original matrix associated with this decomposition, and X and B are matrices.
boolean	leftSolve(Vector x, Vector b) Computes a left solution to the linear equation x M = b where M is the original matrix associated with this decomposition, and x and b are row vectors.
boolean	leftSolveR(DenseMatrix X, Matrix B) Computes a left solution to the linear equation
boolean	leftSolveR(Vector x, Vector b) Computes a left solution to the linear equation
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 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
boolean	solveR(Vector x, Vector b) Computes a solution to the linear equation

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

getR

public MatrixNd getR()

Returns the R matrix associated with this QR decomposition.

Returns:

R matrix

Throws:

ImproperStateException - if this QRDecomposition is uninitialized

getQ

public MatrixNd getQ()

Returns the Q matrix associated with this QR decomposition.

Returns:

Q matrix

Throws:

ImproperStateException - if this QRDecomposition is uninitialized

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 solution to the linear equation
M x = b
where M is the original matrix associated with this decomposition, and x and b are vectors. If M has size m X n with m > n, then the system is overdetermined and solution with the minimum least square error is computed. Alternatively, if m < n, then the system is underdetermined and the a solution is found by using only the left-most m X m block of R (which is the same method used by the MATLAB \ operator).

Parameters:

x - unknown vector to solve for

b - constant vector

Returns:

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

Throws:

ImproperStateException - if this decomposition is uninitialized

ImproperSizeException - 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. If M has size m X n with m > n, then the system is overdetermined and solution with the minimum least square error is computed. Alternatively, if m < n, then the system is underdetermined and the a solution is found by using only the left-most m X m block of R (which is the same method used by the MATLAB \ operator).

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 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.

leftSolve

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

Computes a left solution to the linear equation
x M = b
where M is the original matrix associated with this decomposition, and x and b are row vectors.

The number of rows m in M must equal or exceed the number of columns n (which implies that R is a square matrix with a size equal to n).

Parameters:

x - unknown vector to solve for

b - constant vector

Returns:

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

Throws:

ImproperStateException - if this decomposition is uninitialized or if m < n for the original matrix

ImproperSizeException - 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.

leftSolve

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

Computes a left solution to the linear equation
x M = b
where M is the original matrix associated with this decomposition, and X and B are matrices.

The number of rows m in M must equal or exceed the number of columns n (which implies that R is a square matrix with a size equal to n).

Parameters:

X - unknown matrix to solve for

B - constant matrix

Returns:

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

Throws:

ImproperStateException - if this decomposition is uninitialized or if m < n for the original matrix

ImproperSizeException - 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.

solveR

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

Computes a solution to the linear equation

 R P^T x = b
 

where R is the upper triangular matrix associated with this decomposition, P is the permutation matrix (which is the identity unless the decomposition was formed with factorWithPivoting(maspack.matrix.Matrix)), and x and b are vectors.

If the original matrix M has size m X n, and m >= n, then R is a square matrix with a size equal to n, and x and b should each have size n. Otherise, if m < n, then R is m X n, b should have size m, and x will have size n and will be solved using only the left-most m X m block of R with trailing elements set to zero.

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 P^T X = B
 

where R is the upper triangular matrix associated with this decomposition, P is the permutation matrix (which is the identity unless the decomposition was formed with factorWithPivoting(maspack.matrix.Matrix)), and X and B are matrices.

If the original matrix M has size m X n, and m >= n, then R is a square matrix with a size equal to n, and X and B should each have n rows. Otherise, if m < n, then R is m X n, B should have m rows, and X will have n rows and will be solved using only the left-most m X m block of R with trailing elements set to zero.

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 P^T = b
 

where R is the upper triangular matrix associated with this decomposition, P is the permutation matrix (which is the identity unless the decomposition was formed with factorWithPivoting(maspack.matrix.Matrix)), and x and b are matrices.

The number of rows m in the original matrix M must equal or exceed the number of columns n (which implies that R is a square matrix with a size equal to n). x and b should each have size n.

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 or if m < n for the original matrix

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 P^T = B
 

where R is the upper triangular matrix associated with this decomposition, P is the permutation matrix (which is the identity unless the decomposition was formed with factorWithPivoting(maspack.matrix.Matrix)), and X and B are matrices.

The number of rows m in the original matrix M must equal or exceed the number of columns n (which implies that R is a square matrix with a size equal to n). X and B should each have n rows.

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 or if m < n for the original matrix

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. If the number of rows in the original matrix M is less than the number of columns, the condition number is estimated for the left-most m X m block of R. 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

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)