public class QRDecomposition
extends java.lang.Object
M = Q Rwhere 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 Rwhere 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 and Description |
|---|
QRDecomposition()
Creates an uninitialized QRDecomposition.
|
QRDecomposition(Matrix M)
Creates a QRDecomposition for the Matrix specified by M.
|
| Modifier and Type | Method and Description |
|---|---|
int |
absRank(double tol)
Assess rank of the decomposed matrix using an absolute tolerance on the
values of the R matrix diagonal.
|
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.
|
int[] |
getColumnPermutation()
Returns the indices
cperm of the column permutation matrix P,
such that j-th column of M P is given by column cperm[j]
of M. |
MatrixNd |
getP()
Returns the permutation matrix P associated with this QR decomposition.
|
MatrixNd |
getQ()
Returns the Q matrix associated with this QR decomposition.
|
MatrixNd |
getQ(int numc)
Returns the submatrix of Q corresponding to its first
numc
columns. |
MatrixNd |
getR()
Returns the R matrix associated with this QR decomposition.
|
double |
getR00()
Returns the upper left (0,0) entry of the R matrix.
|
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 |
leftSolve(Vector x,
Vector b,
int ncols)
Computes a left solution to the linear equation
x M = b using only the first ncols columns of the R matrix. |
boolean |
leftSolveR(DenseMatrix X,
Matrix B)
Computes a left solution to the linear equation
|
boolean |
leftSolveR(DenseMatrix X,
Matrix B,
int ncols)
Computes a left solution to the linear equation
|
boolean |
leftSolveR(Vector x,
Vector b)
Computes a left solution to the linear equation
|
boolean |
leftSolveR(Vector x,
Vector b,
int ncols)
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)
Assess rank of the decomposed matrix using a tolerance relative to the
maximum absolute value of the R matrix diagonal.
|
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
|
public QRDecomposition(Matrix M)
M - matrix to perform the QR decomposition onpublic QRDecomposition()
public void factor(Matrix M)
M - matrix to perform the QR decomposition onpublic void factorInPlace(MatrixNd M)
public void factorWithPivoting(Matrix M)
M - matrix to perform the QR decomposition onpublic MatrixNd getR()
ImproperStateException - if this QRDecomposition is uninitializedpublic double getR00()
ImproperStateException - if this QRDecomposition is uninitializedpublic MatrixNd getQ()
ImproperStateException - if this QRDecomposition is uninitializedpublic MatrixNd getP()
factorWithPivoting(maspack.matrix.Matrix)),
then P is the identity matrix.ImproperStateException - if this QRDecomposition is uninitializedpublic MatrixNd getQ(int numc)
numc
columns.numc - number of columnsImproperStateException - if this QRDecomposition is uninitializedpublic int[] getColumnPermutation()
cperm of the column permutation matrix P,
such that j-th column of M P is given by column cperm[j]
of M. If the factorization was not performed with pivoting,
the P is the identity matrix, and cperm will be
simply [ 0 1 2 ... ].
P can be reconstructed from cperm by setting each of its
j columns so that row cperm[j] is 1.
ImproperStateException - if this QRDecomposition is uninitializedpublic void get(MatrixNd Q, MatrixNd R) throws ImproperStateException, ImproperSizeException
get(Q,R,cperm).Q - returns the orthogonal matrixR - returns the upper triangular matrix.ImproperStateException - if this QRDecomposition is uninitializedImproperSizeException - if Q or R are not of the proper dimension and cannot be resized.public void get(MatrixNd Q, MatrixNd R, int[] cperm) throws ImproperStateException, ImproperSizeException
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.Q - returns the orthogonal matrixR - returns the upper triangular matrixcperm - returns the indices of the column permutation matrix P, such that j-th
column of M P is given by column cperm[j] of M.ImproperStateException - if this QRDecomposition is uninitializedImproperSizeException - if Q or R are not of the proper dimension and cannot be resized.public boolean solve(Vector x, Vector b) throws ImproperStateException, ImproperSizeException
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).x - unknown vector to solve forb - constant vectorImproperStateException - if this decomposition is uninitializedImproperSizeException - 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.public boolean solve(DenseMatrix X, Matrix B) throws ImproperStateException, ImproperSizeException
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).X - unknown matrix to solve forB - constant matrixImproperStateException - if this decomposition is uninitializedImproperSizeException - 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.public boolean leftSolve(Vector x, Vector b) throws ImproperStateException, ImproperSizeException
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).
x - unknown vector to solve forb - constant vectorImproperStateException - if this decomposition is uninitialized or if m < n for
the original matrixImproperSizeException - 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.public boolean leftSolve(Vector x, Vector b, int ncols) throws ImproperStateException, ImproperSizeException
ncols columns of the R matrix. M is the decomposed
matrix and x and b are row vectors, and ncols must be <=
the minimum dimension of M. If the decomposition was performed with
pivoting (using factorWithPivoting(maspack.matrix.Matrix)), then the rank of M
can be found (using rank(double) or absRank(double)) and used to
determine ncols, thus allowing solutions of rank-deficient
systems.
The size of b should equal the number of columns of M n. If ncols < n, and the decomposition was performed without
pivoting, then only the first n entries are used. Otherwise, if
the decomposition was performed with pivoting, then only the entries with
indices corresponding to the first n values of cperm[]
are used, where cperm[] is the array returned by getColumnPermutation().
Unlike with leftSolve(Vector,Vector), it is not necessary for
the number of rows in M to equal or exceed the number of columns.
x - unknown vector to solve forb - constant vectorncols - number of columns of R to use in the solutionncols of M do not have full rank
(within working precision)ImproperStateException - if this decomposition has not been initialized with pivotingImproperSizeException - if the size of b is not equal to the number of columns of M,
or if x does not have a size compatible with M and cannot be
resized.public boolean leftSolve(DenseMatrix X, Matrix B) throws ImproperStateException, ImproperSizeException
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).
X - unknown matrix to solve forB - constant matrixImproperStateException - if this decomposition is uninitialized or if m < n for
the original matrixImproperSizeException - 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.public boolean solveR(Vector x, Vector b) throws ImproperStateException, ImproperSizeException
R P^T x = bwhere 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.
x - unknown vector to solve forb - constant vectorImproperStateException - if this decomposition is uninitializedImproperSizeException - 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.public boolean solveR(DenseMatrix X, Matrix B) throws ImproperStateException, ImproperSizeException
R P^T X = Bwhere 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.
X - unknown matrix to solve forB - constant matrixImproperStateException - if this decomposition is uninitializedImproperSizeException - 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.public boolean leftSolveR(Vector x, Vector b) throws ImproperStateException, ImproperSizeException
x R = b Pwhere 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.
x - unknown vector to solve forb - constant vectorImproperStateException - if this decomposition is uninitialized or if m < n for
the original matrixImproperSizeException - 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.public boolean leftSolveR(Vector x, Vector b, int ncols) throws ImproperStateException, ImproperSizeException
x Rsub = b Psubwhere
Rsub is the top-left ncols X ncols submatrix of R,
Psub is formed from the first ncols of the permutation
matrix P, and x and b are row vectors. P is the
identity unless the decomposition was formed with factorWithPivoting(maspack.matrix.Matrix)).
Unlike with leftSolveR(Vector,Vector), it is not necessary
for the number of rows in M to equal or exceed the number of columns.
However, ncols must be <= the minimum matrix dimension.
Often, ncols will be set to the rank of R (which is also the rank
of the original matrix), which can be found (using rank(double) or
absRank(double))
b should have a size equal to the number of original matrix
columns, although only the values of b whose indices are given by
the first ncols entries of the column permutation cperm[]
(returned by getColumnPermutation()) will be used. x
should have a size of ncols or be resizable.
x - unknown vector to solve forb - constant vectorncols - size of the Rsub submatrixImproperStateException - if this decomposition is uninitializedImproperSizeException - if ncols exceeds the minimum
dimension of the original matrix M, if b does not have a size equal to
the original number of matrix columns, or if x does not have size ncols and cannot be resized.public boolean leftSolveR(DenseMatrix X, Matrix B) throws ImproperStateException, ImproperSizeException
X R P^T = Bwhere 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.
X - unknown matrix to solve forB - constant matrixImproperStateException - if this decomposition is uninitialized or if m < n for
the original matrixImproperSizeException - 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.public boolean leftSolveR(DenseMatrix X, Matrix B, int ncols) throws ImproperStateException, ImproperSizeException
X Rsub = B Psubwhere
Rsub is the top-left ncols X ncols submatrix of R,
Psub is formed from the first ncols of the permutation
matrix P, and X and B are matrics. P is the
identity unless the decomposition was formed with factorWithPivoting(maspack.matrix.Matrix)).
Unlike with leftSolveR(Vector,Vector), it is not necessary
for the number of rows in M to equal or exceed the number of columns.
However, ncols must be <= the minimum matrix dimension.
Often, ncols will be set to the rank of R (which is also the rank
of the original matrix), which can be found (using rank(double) or
absRank(double))
The number of columns of B should equal the number of columns of the
original matrix, although only the columns of B whose indices are
given by the first ncols entries of the column permutation cperm[] (returned by getColumnPermutation()) will be used.
X should either be resizable or should have ncols columns
and the same number of rows as X.
X - unknown matrix solve forB - constant matrixncols - size of the R submatrixImproperStateException - if this decomposition is uninitializedImproperSizeException - if ncols exceeds the minimum
dimension of the original matrix M, if B does not have the same column
size as the original matrix, or if X is not resizable and does not have
ncols columns and a row size equal to X.public double conditionEstimate()
throws ImproperStateException
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).ImproperStateException - if this QRDecomposition is uninitializedpublic double determinant()
throws ImproperStateException
ImproperStateException - if this decomposition is uninitializedpublic boolean inverse(DenseMatrix X) throws ImproperStateException
X - matrix in which the inverse is storedImproperStateException - if this decomposition is uninitializedImproperSizeException - if M is not square, or if X does not have the same size as M and cannot be
resized.public int rank(double tol)
tol - relative tolerancepublic int absRank(double tol)
tol - absolute tolerancepublic void preMulQ(MatrixNd MR, MatrixNd M1)
MR = Q M1where 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.
MR - result matrixM1 - matrix to pre-multiply by Qpublic void preMulQTranspose(MatrixNd MR, MatrixNd M1)
MR = Q^T M1where 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.
MR - result matrixM1 - matrix to pre-multiply by Q transposepublic void postMulQ(MatrixNd MR, MatrixNd M1)
MR = M1 Qwhere 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.
MR - result matrixM1 - matrix to post-multiply by Qpublic void postMulQTranspose(MatrixNd MR, MatrixNd M1)
MR = M1 Q^Twhere 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.
MR - result matrixM1 - matrix to post-multiply by Q transposepublic static void main(java.lang.String[] args)