Class SymmetricQRAlgorithm
- java.lang.Object
-
- dev.nm.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.
-
-
Constructor Summary
Constructors Constructor 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 Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
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 matrixepsilon
- 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 matrixepsilon
- a precision parameter: when a number |x| ≤ ε, it is considered 0maxIterations
- 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 interfaceSpectrum
- Returns:
- the list of eigenvalues
-
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
- See Also:
- "James W. Demmel, Applied Numerical Linear Algebra, SIAM; 1 edition (August 1, 1997)."
-
getEigenvectors
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 methodgetEigenvalues()
.- Returns:
- the eigenvectors of A
-
-