# SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.eigen.qr

## Class QRAlgorithm

• java.lang.Object
• com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.eigen.qr.QRAlgorithm
• All Implemented Interfaces:
Spectrum

public class QRAlgorithm
extends Object
implements Spectrum
The QR algorithm is an eigenvalue algorithm by computing the real Schur canonical form of a matrix. That is, Q'AQ = T where Q is orthogonal, and T is quasi-triangular. The eigenvalues of A are the same as those of the diagonal blocks in T. The basic idea of the procedure is to perform the QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the opposite order, and iterate.

This implementation is the implicit double-shift version. It makes the use of multiple shifts easier to introduce. The matrix is first brought to the upper Hessenberg form: A0 = QAQ' as in the explicit version; then, at each step, the first column of Ak is transformed via a small-size Householder similarity transformation to the first column of p(Ak)e1, where p(Ak), of degree r, is the polynomial that defines the shifting strategy. Then successive Householder transformation of size r+1 are performed in order to return the working matrix Ak to the upper Hessenberg form. This operation is known as bulge chasing, due to the peculiar shape of the non-zero entries of the matrix along the steps of the algorithm. Deflation is performed as soon as one of the sub-diagonal entries of Ak is sufficiently small. No QR decomposition is explicitly performed. Instead, we use the Francis algorithm (FrancisQRStep), as described in Golub and Van Loan.

Wikipedia: QR algorithm
• ### Constructor Summary

Constructors
Constructor and Description
QRAlgorithm(Matrix A)
Runs the QR algorithm on a square matrix.
QRAlgorithm(Matrix A, double epsilon)
Runs the QR algorithm on a square matrix.
QRAlgorithm(Matrix A, double epsilon, int maxIterations)
Runs the QR algorithm on a square matrix.
• ### Method Summary

All Methods
Modifier and Type Method and Description
List<Number> getEigenvalues()
Get all the eigenvalues.
List<Vector> getEigenVectors()
Matrix Q()
Gets the Q matrix as in the real Schur canonical form Q'AQ = T.
List<Matrix> Qs()
Gets the list of Qi's produced in the process of the QR algorithm (if keepQs is set to true).
Matrix T()
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### QRAlgorithm

public QRAlgorithm(Matrix A)
Runs the QR algorithm on a square matrix. The algorithm loops until H becomes quasi-triangular.
Parameters:
A - a matrix
Throws:
IllegalArgumentException - if A is not square
• #### QRAlgorithm

public QRAlgorithm(Matrix A,
double epsilon)
Runs the QR algorithm on a square matrix. The algorithm loops until H becomes quasi-triangular.
Parameters:
A - a square matrix
epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0
• #### QRAlgorithm

public QRAlgorithm(Matrix A,
double epsilon,
int maxIterations)
Runs the QR algorithm on a square matrix. The algorithm is a convergence algorithm. It stops when either
1. H becomes quasi-triangular, or
2. the maximum number of iterations is reached.
By default, intermediate Qi's are not kept.
Parameters:
A - a square matrix
epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0
maxIterations - the maximum number of iterations
Throws:
IllegalArgumentException - if A is not square
• ### Method Detail

• #### getEigenvalues

public List<Number> getEigenvalues()
Get all the eigenvalues. Given a Hessenberg matrix, $\begin{bmatrix} H_{11} & H_{12} & H_{13}\\ 0 & H_{22} & H_{23}\\ 0 & 0 & H_{33} \end{bmatrix}$ the real Schur canonical form is Q'HQ = T, where Q is orthogonal, and T is quasi-triangular.

This implementation is a modified version of the algorithm in the reference.

Specified by:
getEigenvalues in interface Spectrum
Returns:
the list of eigenvalues
"G. H. Golub, C. F. van Loan, "Algorithm 7.5.2," Matrix Computations, 3rd edition."
• #### Qs

public List<Matrix> Qs()
Gets the list of Qi's produced in the process of the QR algorithm (if keepQs is set to true).
Returns:
the list of Qi's
• #### Q

public Matrix Q()
Gets the Q matrix as in the real Schur canonical form Q'AQ = T. The columns of Q are called Schur vectors. If T is diagonal, then the Schur vectors are the eigenvectors.

This implementation stores all the Qi's produced in the process of the QR algorithm. Q is a product of them. That is, $Q = (Q_1 \times ... \times Q_n)$

Returns:
Q
• #### T

public Matrix T()
• #### getEigenVectors

public List<Vector> getEigenVectors()