Class SchurTransformer


  • class SchurTransformer
    extends java.lang.Object
    Class transforming a general real matrix to Schur form.

    A m × m matrix A can be written as the product of three matrices: A = P × T × PT with P an orthogonal matrix and T an quasi-triangular matrix. Both P and T are m × m matrices.

    Transformation to Schur form is often not a goal by itself, but it is an intermediate step in more general decomposition algorithms like eigen decomposition. This class is therefore intended for internal use by the library and is not public. As a consequence of this explicitly limited scope, many methods directly returns references to internal arrays, not copies.

    This class is based on the method hqr2 in class EigenvalueDecomposition from the JAMA library.

    Since:
    3.1
    See Also:
    Schur Decomposition - MathWorld, Schur Decomposition - Wikipedia, Householder Transformations
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private static class  SchurTransformer.ShiftInfo
      Internal data structure holding the current shift information.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private RealMatrix cachedP
      Cached value of P.
      private RealMatrix cachedPt
      Cached value of PT.
      private RealMatrix cachedT
      Cached value of T.
      private double epsilon
      Epsilon criteria taken from JAMA code (originally was 2^-52).
      private double[][] matrixP
      P matrix.
      private double[][] matrixT
      T matrix.
      private static int MAX_ITERATIONS
      Maximum allowed iterations for convergence of the transformation.
    • Constructor Summary

      Constructors 
      Constructor Description
      SchurTransformer​(RealMatrix matrix)
      Build the transformation to Schur form of a general real matrix.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void computeShift​(int l, int idx, int iteration, SchurTransformer.ShiftInfo shift)
      Compute the shift for the current iteration.
      private int findSmallSubDiagonalElement​(int startIdx, double norm)
      Find the first small sub-diagonal element and returns its index.
      private double getNorm()
      Computes the L1 norm of the (quasi-)triangular matrix T.
      RealMatrix getP()
      Returns the matrix P of the transform.
      RealMatrix getPT()
      Returns the transpose of the matrix P of the transform.
      RealMatrix getT()
      Returns the quasi-triangular Schur matrix T of the transform.
      private int initQRStep​(int il, int iu, SchurTransformer.ShiftInfo shift, double[] hVec)
      Initialize the householder vectors for the QR step.
      private void performDoubleQRStep​(int il, int im, int iu, SchurTransformer.ShiftInfo shift, double[] hVec)
      Perform a double QR step involving rows l:idx and columns m:n
      private void transform()
      Transform original matrix to Schur form.
      • Methods inherited from class java.lang.Object

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

      • MAX_ITERATIONS

        private static final int MAX_ITERATIONS
        Maximum allowed iterations for convergence of the transformation.
        See Also:
        Constant Field Values
      • matrixP

        private final double[][] matrixP
        P matrix.
      • matrixT

        private final double[][] matrixT
        T matrix.
      • cachedP

        private RealMatrix cachedP
        Cached value of P.
      • cachedT

        private RealMatrix cachedT
        Cached value of T.
      • cachedPt

        private RealMatrix cachedPt
        Cached value of PT.
      • epsilon

        private final double epsilon
        Epsilon criteria taken from JAMA code (originally was 2^-52).
    • Constructor Detail

      • SchurTransformer

        SchurTransformer​(RealMatrix matrix)
        Build the transformation to Schur form of a general real matrix.
        Parameters:
        matrix - matrix to transform
        Throws:
        NonSquareMatrixException - if the matrix is not square
    • Method Detail

      • getP

        public RealMatrix getP()
        Returns the matrix P of the transform.

        P is an orthogonal matrix, i.e. its inverse is also its transpose.

        Returns:
        the P matrix
      • getPT

        public RealMatrix getPT()
        Returns the transpose of the matrix P of the transform.

        P is an orthogonal matrix, i.e. its inverse is also its transpose.

        Returns:
        the transpose of the P matrix
      • getT

        public RealMatrix getT()
        Returns the quasi-triangular Schur matrix T of the transform.
        Returns:
        the T matrix
      • transform

        private void transform()
        Transform original matrix to Schur form.
        Throws:
        MaxCountExceededException - if the transformation does not converge
      • getNorm

        private double getNorm()
        Computes the L1 norm of the (quasi-)triangular matrix T.
        Returns:
        the L1 norm of matrix T
      • findSmallSubDiagonalElement

        private int findSmallSubDiagonalElement​(int startIdx,
                                                double norm)
        Find the first small sub-diagonal element and returns its index.
        Parameters:
        startIdx - the starting index for the search
        norm - the L1 norm of the matrix
        Returns:
        the index of the first small sub-diagonal element
      • computeShift

        private void computeShift​(int l,
                                  int idx,
                                  int iteration,
                                  SchurTransformer.ShiftInfo shift)
        Compute the shift for the current iteration.
        Parameters:
        l - the index of the small sub-diagonal element
        idx - the current eigenvalue index
        iteration - the current iteration
        shift - holder for shift information
      • initQRStep

        private int initQRStep​(int il,
                               int iu,
                               SchurTransformer.ShiftInfo shift,
                               double[] hVec)
        Initialize the householder vectors for the QR step.
        Parameters:
        il - the index of the small sub-diagonal element
        iu - the current eigenvalue index
        shift - shift information holder
        hVec - the initial houseHolder vector
        Returns:
        the start index for the QR step
      • performDoubleQRStep

        private void performDoubleQRStep​(int il,
                                         int im,
                                         int iu,
                                         SchurTransformer.ShiftInfo shift,
                                         double[] hVec)
        Perform a double QR step involving rows l:idx and columns m:n
        Parameters:
        il - the index of the small sub-diagonal element
        im - the start index for the QR step
        iu - the current eigenvalue index
        shift - shift information holder
        hVec - the initial houseHolder vector