# SuanShu, a Java numerical and statistical library

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

## Class SymmetricQRAlgorithm

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

public class SymmetricQRAlgorithm
extends Object
implements Spectrum
The symmetric QR algorithm is an eigenvalue algorithm by computing the real Schur canonical form of a square, symmetric matrix. That is, Q'AQ = D where Q is orthogonal, and D is diagonal. The eigenvalues of A are the same as those of the diagonal entries of D. And the columns of Q are the eigenvectors of A. The basic idea of the algorithm is first reducing the symmetric matrix to a tridiagonal matrix, and then using Givens rotations to eliminate the off diagonal elements.

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 tridiagonal form: A0 = Q0'AQ0 as in the explicit version; then, at each step, the element at 1st column, 2nd row of $$A_k-\mu I$$ is zeroed out via a small-size Givens rotation. where $$\mu$$ is the shift. Then successive Givens rotations are performed in order to return the working matrix Ak to the tridiagonal 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 off-diagonal entries of Ak is sufficiently small. No QR decomposition is explicitly performed. Instead, we use the Implicit Symmetric QR Step with Wilkinson Shift, as described in Golub and Van Loan.

"Golub, G. H., van Loan, C. F., "Algorithm 8.3.2, Algorithm 8.3.3" Matrix Computations, 3rd edition."
• ### Constructor Summary

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

All Methods
Modifier and Type Method and Description
Matrix D()
Gets the D matrix as in the real Schur canonical form Q'AQ = D.
List<Double> getEigenvalues()
Get all the eigenvalues.
List<Vector> getEigenvectors()
Gets the eigenvectors of A, which are the columns of Q.
List<GivensMatrix> Gs()
Gets the list of Gk's produced in the process of diagonalizing the tridiagonal matrix.
Matrix Q()
Gets the Q matrix as in Q'AQ = D, where D is diagonal and Q is orthogonal.
• ### Methods inherited from class java.lang.Object

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

• #### SymmetricQRAlgorithm

public SymmetricQRAlgorithm(Matrix A)
Runs the QR algorithm on a symmetric matrix. The algorithm stops when D becomes diagonal.
Parameters:
A - a symmetric matrix
Throws:
IllegalArgumentException - if A is not symmetric
• #### SymmetricQRAlgorithm

public SymmetricQRAlgorithm(Matrix A,
double epsilon)
Runs the QR algorithm on a symmetric matrix. The algorithm stops when D becomes diagonal.
Parameters:
A - a symmetric matrix
epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0
• #### SymmetricQRAlgorithm

public SymmetricQRAlgorithm(Matrix A,
double epsilon,
int maxIterations)
Runs the QR algorithm on a symmetric matrix. The algorithm stops when D becomes diagonal.
Parameters:
A - a symmetric 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 symmetric
• ### Method Detail

• #### getEigenvalues

public List<Double> getEigenvalues()
Get all the eigenvalues.

Given a tridiagonal matrix, T, $\begin{bmatrix} a_{1} & b_{2} & 0 & 0\\ b_{2} & a_{2} & b_{3}& 0\\ 0 & b_{3} & a_{3}& b_{4}\\ 0 & 0 & b_{4}& a_{4} \end{bmatrix}$ the real Schur canonical form is Q'TQ = D, where Q is orthogonal, and D is diagonal.

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

Specified by:
getEigenvalues in interface Spectrum
Returns:
the list of eigenvalues
"Golub, G. H., Van Loan, C. F., "Algorithm 8.3.2 and Algorithm 8.3.3", Matrix Computations, 3rd edition."
• #### Gs

public List<GivensMatrix> Gs()
Gets the list of Gk's produced in the process of diagonalizing the tridiagonal matrix.
Returns:
the list of Gk's
• #### Q

public Matrix Q()
Gets the Q matrix as in Q'AQ = D, where D is diagonal and Q is orthogonal. The columns of Q are the eigenvectors of A.

This implementation stores all the Givens matrix Gk's produced in the process of diagonalizing the tridiagonal matrix. Q is a product of them and the rotation matrix,Q0 which tridiagonalizes A. That is, $Q = (Q_0\timesG_1 \times ... \times G_n)$

Returns:
Q
• #### D

public Matrix D()
Gets the D matrix as in the real Schur canonical form Q'AQ = D. D is diagonal. The eigenvectors of A are columns of Q.
Returns:
D
public List<Vector> getEigenvectors()
Gets the eigenvectors of A, which are the columns of Q. The order of the eigenvectors matches the order of corresponding eigenvalues returned by the method getEigenvalues().