edu.stanford.rsl.konrad.numerics
Class DecompositionQR

java.lang.Object
  extended by edu.stanford.rsl.konrad.numerics.DecompositionQR

public class DecompositionQR
extends java.lang.Object

Implements a QR decomposition for arbitrary matrices. This functor object allows to decompose any matrix \f$ \mathbf{A} \f$ into matrices \f$ \mathbf{Q} \f$ and \f$ \mathbf{R} \f$ such that \f[ \mathbf{A} = \mathbf{Q} \mathbf{R}. \f] Use it for solving systems of linear equations and for minimization problems (with more equations than variables). The QR decomposition is not suited for computing the set of solutions for an under-determined system of equations (although it may be used to compute one of those solutions). Assuming \f$ \mathbf A \f$ is a \f$ m \times n \f$ matrix, the decomposition is performed such that the matrix \f$ \mathbf Q \f$ has dimensions \f$ m \times m \f$ and is orthogonal and the matrix \f$ \mathbf{R} \f$ has dimensions \f$ m \times n \f$ and has upper triangular form (\f$ r_{i,j} = 0 \f$ for \f$ i>j \f$). Internally, only a compressed version of the factors \f$ \mathbf{Q} \f$ and \f$ \mathbf{R} \f$ is stored which together needs approximately as much space as the original matrix \f$ \mathbf{A} \f$. Usage: \code Nude::Decomposition::QR<> qr; qr(A); qr.solve(b); \endcode \sa RQ \sa Deuflhard/Hohmann: Numerische Mathematik I \sa The development of this code started out with the implementation of TNT/JAMA at http://math.nist.gov/tnt/. However, it was completely revised, optimized, and commented. \author Andreas Keil \todo Handle singularity / do pivoting when decomposing. \todo Improve method isFullRank() to check against an epsilon.


Constructor Summary
DecompositionQR(SimpleMatrix A)
          Constructor performing the actual decomposition of a matrix $\mathbf{A}$ and storing the result in an internal format.
 
Method Summary
 SimpleMatrix getQ()
          Compute Q from the internal storage QR.
 SimpleMatrix getR()
          Compute R from the internal storages QR and Rdiag.
 boolean isFullRank()
          Specifies whether the input Matrix $A$ has full rank.
 SimpleMatrix solve(SimpleMatrix B)
          Computes solution Matrix $\mathbf X$ for the right-hand-side $\mathbf B$.
 SimpleVector solve(SimpleVector b)
          Computes solution Vector $\mathbf x$ for the right-hand-side $\mathbf b$.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DecompositionQR

public DecompositionQR(SimpleMatrix A)
Constructor performing the actual decomposition of a matrix $\mathbf{A}$ and storing the result in an internal format. Decomposition is performed as soon as a Matrix is given to this constructor and the result is stored internally. Afterwards, the other other members (solve(SimpleVector b), solve(SimpleMatrix B), getQ(), and getR()) can be used multiple times without having to recompute the decomposition.

Parameters:
A - The Matrix to be decomposed.
Method Detail

isFullRank

public boolean isFullRank()
Specifies whether the input Matrix $A$ has full rank.

Returns:
Whether the input Matrix has full rank ($\min\{m, n\}$).

solve

public SimpleVector solve(SimpleVector b)
Computes solution Vector $\mathbf x$ for the right-hand-side $\mathbf b$. Depending on the size of $\mathbf A \in \mathbb{R}^{m \times n}$, the problem task can either be the solution of a system of equations with a unique solution or a minimization task: task:
%preamble{\usepackage{amsmath}} \begin{align}
For $m < n$ the QR decomposition computes one of the infinite number of solutions to the under-determined system of equations. Better use the RQ decomposition in this case.

Remark: If you want to further improve the accuracy of your solution in case (1), perform a correction step in the following manner:
x = qr.solve(b); x += qr.solve(b - A*x);

Parameters:
b - The right-hand-side Vector.
Returns:
The solution Vector $\mathbf x$.
See Also:
solve(SimpleMatrix)

solve

public SimpleMatrix solve(SimpleMatrix B)
Computes solution Matrix $\mathbf X$ for the right-hand-side $\mathbf B$. This method does the same as solve(SimpleVector) but for multiple right-hand-side vectors, given as a Matrix.

Parameters:
B - The right-hand-side Matrix for which a solution is computed column-wise.
Returns:
The solution Matrix $\mathbf X$.
See Also:
solve(SimpleVector)

getR

public SimpleMatrix getR()
Compute R from the internal storages QR and Rdiag. R has the same dimensions as the original matrix. An economy-sized version would only return the non-zero submatrix.


getQ

public SimpleMatrix getQ()
Compute Q from the internal storage QR. Q is a square matrix with both dimensions equaling the row number of the original matrix. An economy-sized version would only return the columns of Q corresponding to the economy-sized version of R.