maspack.matrix
Class QRDecomposition

java.lang.Object
  extended by 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
QRDecomposition()
          Creates an uninitialized QRDecomposition.
QRDecomposition(Matrix M)
          Creates a QRDecomposition for the Matrix specified by M.
 
Method Summary
 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)
           
 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)

main

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