org.apache.commons.math3.linear
Class SchurTransformer

java.lang.Object
  extended by org.apache.commons.math3.linear.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
Version:
$Id: SchurTransformer.java 1389129 2012-09-23 19:34:02Z tn $
See Also:
Schur Decomposition - MathWorld, Schur Decomposition - Wikipedia, Householder Transformations

Nested Class Summary
private static class SchurTransformer.ShiftInfo
          Internal data structure holding the current shift information.
 
Field Summary
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
SchurTransformer(RealMatrix matrix)
          Build the transformation to Schur form of a general real matrix.
 
Method Summary
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

public 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


Copyright (c) 2003-2013 Apache Software Foundation