Class 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 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
      • 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 method getEigenvalues().
        Returns:
        the eigenvectors of A