Class 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.

    See Also:
    Wikipedia: QR algorithm
    • 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
      • 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
      • getEigenVectors

        public List<Vector> getEigenVectors()