org.apache.commons.math3.linear

## Class EigenDecomposition

- java.lang.Object
- - org.apache.commons.math3.linear.EigenDecomposition

-     public class EigenDecomposition
      extends java.lang.Object

  Calculates the eigen decomposition of a real matrix.

  The eigen decomposition of matrix A is a set of two matrices: V and D such that A = V × D × VT. A, V and D are all m × m matrices.

  This class is similar in spirit to the `EigenvalueDecomposition` class from the JAMA library, with the following changes:

  - a `getVt` method has been added,
  - two `getRealEigenvalue` and `getImagEigenvalue` methods to pick up a single eigenvalue have been added,
  - a `getEigenvector` method to pick up a single eigenvector has been added,
  - a `getDeterminant` method has been added.
  - a `getSolver` method has been added.

  As of 3.1, this class supports general real matrices (both symmetric and non-symmetric):

  If A is symmetric, then A = V*D*V' where the eigenvalue matrix D is diagonal and the eigenvector matrix V is orthogonal, i.e. A = V.multiply(D.multiply(V.transpose())) and V.multiply(V.transpose()) equals the identity matrix.

  If A is not symmetric, then the eigenvalue matrix D is block diagonal with the real eigenvalues in 1-by-1 blocks and any complex eigenvalues, lambda + i*mu, in 2-by-2 blocks:

          [lambda, mu    ]
          [   -mu, lambda]

  The columns of V represent the eigenvectors in the sense that A*V = V*D, i.e. A.multiply(V) equals V.multiply(D). The matrix V may be badly conditioned, or even singular, so the validity of the equation A = V*D*inverse(V) depends upon the condition of V.

  This implementation is based on the paper by A. Drubrulle, R.S. Martin and J.H. Wilkinson "The Implicit QL Algorithm" in Wilksinson and Reinsch (1971) Handbook for automatic computation, vol. 2, Linear algebra, Springer-Verlag, New-York

  Since:
    2.0 (changed to concrete class in 3.0)
  Version:
    $Id: EigenDecomposition.java 1422195 2012-12-15 06:45:18Z psteitz $
  See Also:
    MathWorld, Wikipedia

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `private static class` | `EigenDecomposition.Solver` Specialized solver.

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `private RealMatrix` | `cachedD` Cached value of D.
    `private RealMatrix` | `cachedV` Cached value of V.
    `private RealMatrix` | `cachedVt` Cached value of Vt.
    `private ArrayRealVector[]` | `eigenvectors` Eigenvectors.
    `private static double` | `EPSILON` Internally used epsilon criteria.
    `private double[]` | `imagEigenvalues` Imaginary part of the realEigenvalues.
    `private boolean` | `isSymmetric` Whether the matrix is symmetric.
    `private double[]` | `main` Main diagonal of the tridiagonal matrix.
    `private byte` | `maxIter` Maximum number of iterations accepted in the implicit QL transformation
    `private double[]` | `realEigenvalues` Real part of the realEigenvalues.
    `private double[]` | `secondary` Secondary diagonal of the tridiagonal matrix.
    `private TriDiagonalTransformer` | `transformer` Transformer to tridiagonal (may be null if matrix is already tridiagonal).

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `EigenDecomposition(double[] main, double[] secondary)` Calculates the eigen decomposition of the symmetric tridiagonal matrix.
    `EigenDecomposition(double[] main, double[] secondary, double splitTolerance)` Deprecated. in 3.1 (to be removed in 4.0) due to unused parameter
    `EigenDecomposition(RealMatrix matrix)` Calculates the eigen decomposition of the given real matrix.
    `EigenDecomposition(RealMatrix matrix, double splitTolerance)` Deprecated. in 3.1 (to be removed in 4.0) due to unused parameter

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `private Complex` | `cdiv(double xr, double xi, double yr, double yi)` Performs a division of two complex numbers.
    `private void` | `findEigenVectors(double[][] householderMatrix)` Find eigenvalues and eigenvectors (Dubrulle et al., 1971)
    `private void` | `findEigenVectorsFromSchur(SchurTransformer schur)` Find eigenvectors from a matrix transformed to Schur form.
    `RealMatrix` | `getD()` Gets the block diagonal matrix D of the decomposition.
    `double` | `getDeterminant()` Computes the determinant of the matrix.
    `RealVector` | `getEigenvector(int i)` Gets a copy of the ith eigenvector of the original matrix.
    `double` | `getImagEigenvalue(int i)` Gets the imaginary part of the ith eigenvalue of the original matrix.
    `double[]` | `getImagEigenvalues()` Gets a copy of the imaginary parts of the eigenvalues of the original matrix.
    `double` | `getRealEigenvalue(int i)` Returns the real part of the ith eigenvalue of the original matrix.
    `double[]` | `getRealEigenvalues()` Gets a copy of the real parts of the eigenvalues of the original matrix.
    `DecompositionSolver` | `getSolver()` Gets a solver for finding the A × X = B solution in exact linear sense.
    `RealMatrix` | `getSquareRoot()` Computes the square-root of the matrix.
    `RealMatrix` | `getV()` Gets the matrix V of the decomposition.
    `RealMatrix` | `getVT()` Gets the transpose of the matrix V of the decomposition.
    `boolean` | `hasComplexEigenvalues()` Returns whether the calculated eigen values are complex or real.
    `private SchurTransformer` | `transformToSchur(RealMatrix matrix)` Transforms the matrix to Schur form and calculates the eigenvalues.
    `private void` | `transformToTridiagonal(RealMatrix matrix)` Transforms the matrix to tridiagonal form.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### EPSILON

          private static final double EPSILON

      Internally used epsilon criteria.
      See Also:
        Constant Field Values

    - #### maxIter

          private byte maxIter

      Maximum number of iterations accepted in the implicit QL transformation

    - #### main

          private double[] main

      Main diagonal of the tridiagonal matrix.

    - #### secondary

          private double[] secondary

      Secondary diagonal of the tridiagonal matrix.

    - #### transformer

          private TriDiagonalTransformer transformer

      Transformer to tridiagonal (may be null if matrix is already tridiagonal).

    - #### realEigenvalues

          private double[] realEigenvalues

      Real part of the realEigenvalues.

    - #### imagEigenvalues

          private double[] imagEigenvalues

      Imaginary part of the realEigenvalues.

    - #### eigenvectors

          private ArrayRealVector[] eigenvectors

      Eigenvectors.

    - #### cachedV

          private RealMatrix cachedV

      Cached value of V.

    - #### cachedD

          private RealMatrix cachedD

      Cached value of D.

    - #### cachedVt

          private RealMatrix cachedVt

      Cached value of Vt.

    - #### isSymmetric

          private final boolean isSymmetric

      Whether the matrix is symmetric.

  - ### Constructor Detail

    - #### EigenDecomposition

          public EigenDecomposition(RealMatrix matrix)
                             throws MathArithmeticException

      Calculates the eigen decomposition of the given real matrix.

      Supports decomposition of a general matrix since 3.1.

      Parameters:
        `matrix` - Matrix to decompose.
      Throws:
        `MaxCountExceededException` - if the algorithm fails to converge.
        `MathArithmeticException` - if the decomposition of a general matrix results in a matrix with zero norm
      Since:
        3.1

    - #### EigenDecomposition

          @Deprecated
          public EigenDecomposition(RealMatrix matrix,
                                       double splitTolerance)
                             throws MathArithmeticException

      Deprecated. in 3.1 (to be removed in 4.0) due to unused parameter
      Calculates the eigen decomposition of the given real matrix.
      Parameters:
        `matrix` - Matrix to decompose.
        `splitTolerance` - Dummy parameter (present for backward compatibility only).
      Throws:
        `MathArithmeticException` - if the decomposition of a general matrix results in a matrix with zero norm
        `MaxCountExceededException` - if the algorithm fails to converge.

    - #### EigenDecomposition

          public EigenDecomposition(double[] main,
                            double[] secondary)

      Calculates the eigen decomposition of the symmetric tridiagonal matrix. The Householder matrix is assumed to be the identity matrix.
      Parameters:
        `main` - Main diagonal of the symmetric tridiagonal form.
        `secondary` - Secondary of the tridiagonal form.
      Throws:
        `MaxCountExceededException` - if the algorithm fails to converge.
      Since:
        3.1

    - #### EigenDecomposition

          @Deprecated
          public EigenDecomposition(double[] main,
                                       double[] secondary,
                                       double splitTolerance)

      Deprecated. in 3.1 (to be removed in 4.0) due to unused parameter
      Calculates the eigen decomposition of the symmetric tridiagonal matrix. The Householder matrix is assumed to be the identity matrix.
      Parameters:
        `main` - Main diagonal of the symmetric tridiagonal form.
        `secondary` - Secondary of the tridiagonal form.
        `splitTolerance` - Dummy parameter (present for backward compatibility only).
      Throws:
        `MaxCountExceededException` - if the algorithm fails to converge.

  - ### Method Detail

    - #### getV

          public RealMatrix getV()

      Gets the matrix V of the decomposition. V is an orthogonal matrix, i.e. its transpose is also its inverse. The columns of V are the eigenvectors of the original matrix. No assumption is made about the orientation of the system axes formed by the columns of V (e.g. in a 3-dimension space, V can form a left- or right-handed system).
      Returns:
        the V matrix.

    - #### getD

          public RealMatrix getD()

      Gets the block diagonal matrix D of the decomposition. D is a block diagonal matrix. Real eigenvalues are on the diagonal while complex values are on 2x2 blocks { {real +imaginary}, {-imaginary, real} }.
      Returns:
        the D matrix.
      See Also:
        `getRealEigenvalues()`, `getImagEigenvalues()`

    - #### getVT

          public RealMatrix getVT()

      Gets the transpose of the matrix V of the decomposition. V is an orthogonal matrix, i.e. its transpose is also its inverse. The columns of V are the eigenvectors of the original matrix. No assumption is made about the orientation of the system axes formed by the columns of V (e.g. in a 3-dimension space, V can form a left- or right-handed system).
      Returns:
        the transpose of the V matrix.

    - #### hasComplexEigenvalues

          public boolean hasComplexEigenvalues()

      Returns whether the calculated eigen values are complex or real.

      The method performs a zero check for each element of the `getImagEigenvalues()` array and returns `true` if any element is not equal to zero.

      Returns:
        `true` if the eigen values are complex, `false` otherwise
      Since:
        3.1

    - #### getRealEigenvalues

          public double[] getRealEigenvalues()

      Gets a copy of the real parts of the eigenvalues of the original matrix.
      Returns:
        a copy of the real parts of the eigenvalues of the original matrix.
      See Also:
        `getD()`, `getRealEigenvalue(int)`, `getImagEigenvalues()`

    - #### getRealEigenvalue

          public double getRealEigenvalue(int i)

      Returns the real part of the ith eigenvalue of the original matrix.
      Parameters:
        `i` - index of the eigenvalue (counting from 0)
      Returns:
        real part of the ith eigenvalue of the original matrix.
      See Also:
        `getD()`, `getRealEigenvalues()`, `getImagEigenvalue(int)`

    - #### getImagEigenvalues

          public double[] getImagEigenvalues()

      Gets a copy of the imaginary parts of the eigenvalues of the original matrix.
      Returns:
        a copy of the imaginary parts of the eigenvalues of the original matrix.
      See Also:
        `getD()`, `getImagEigenvalue(int)`, `getRealEigenvalues()`

    - #### getImagEigenvalue

          public double getImagEigenvalue(int i)

      Gets the imaginary part of the ith eigenvalue of the original matrix.
      Parameters:
        `i` - Index of the eigenvalue (counting from 0).
      Returns:
        the imaginary part of the ith eigenvalue of the original matrix.
      See Also:
        `getD()`, `getImagEigenvalues()`, `getRealEigenvalue(int)`

    - #### getEigenvector

          public RealVector getEigenvector(int i)

      Gets a copy of the ith eigenvector of the original matrix.
      Parameters:
        `i` - Index of the eigenvector (counting from 0).
      Returns:
        a copy of the ith eigenvector of the original matrix.
      See Also:
        `getD()`

    - #### getDeterminant

          public double getDeterminant()

      Computes the determinant of the matrix.
      Returns:
        the determinant of the matrix.

    - #### getSquareRoot

          public RealMatrix getSquareRoot()

      Computes the square-root of the matrix. This implementation assumes that the matrix is symmetric and postive definite.
      Returns:
        the square-root of the matrix.
      Throws:
        `MathUnsupportedOperationException` - if the matrix is not symmetric or not positive definite.
      Since:
        3.1

    - #### getSolver

          public DecompositionSolver getSolver()

      Gets a solver for finding the A × X = B solution in exact linear sense.

      Since 3.1, eigen decomposition of a general matrix is supported, but the `DecompositionSolver` only supports real eigenvalues.

      Returns:
        a solver
      Throws:
        `MathUnsupportedOperationException` - if the decomposition resulted in complex eigenvalues

    - #### transformToTridiagonal

          private void transformToTridiagonal(RealMatrix matrix)

      Transforms the matrix to tridiagonal form.
      Parameters:
        `matrix` - Matrix to transform.

    - #### findEigenVectors

          private void findEigenVectors(double[][] householderMatrix)

      Find eigenvalues and eigenvectors (Dubrulle et al., 1971)
      Parameters:
        `householderMatrix` - Householder matrix of the transformation to tridiagonal form.

    - #### transformToSchur

          private SchurTransformer transformToSchur(RealMatrix matrix)

      Transforms the matrix to Schur form and calculates the eigenvalues.
      Parameters:
        `matrix` - Matrix to transform.
      Returns:
        the `Shur transform` for this matrix

    - #### cdiv

          private Complex cdiv(double xr,
                     double xi,
                     double yr,
                     double yi)

      Performs a division of two complex numbers.
      Parameters:
        `xr` - real part of the first number
        `xi` - imaginary part of the first number
        `yr` - real part of the second number
        `yi` - imaginary part of the second number
      Returns:
        result of the complex division

    - #### findEigenVectorsFromSchur

          private void findEigenVectorsFromSchur(SchurTransformer schur)
                                          throws MathArithmeticException

      Find eigenvectors from a matrix transformed to Schur form.
      Parameters:
        `schur` - the schur transformation of the matrix
      Throws:
        `MathArithmeticException` - if the Schur form has a norm of zero

Copyright (c) 2003-2013 Apache Software Foundation