org.apache.commons.math.linear

## Class EigenDecompositionImpl

- java.lang.Object
- - org.apache.commons.math.linear.EigenDecompositionImpl

- All Implemented Interfaces:
    EigenDecomposition

      public class EigenDecompositionImpl
      extends Object
      implements EigenDecomposition

  Calculates the eigen decomposition of a real symmetric 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.

  As of 2.0, this class supports only symmetric matrices, and hence computes only real realEigenvalues. This implies the D matrix returned by `getD()` is always diagonal and the imaginary values returned `getImagEigenvalue(int)` and `getImagEigenvalues()` are always null.

  When called with a `RealMatrix` argument, this implementation only uses the upper part of the matrix, the part below the diagonal is not accessed at all.

  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
  Version:
    $Revision: 1002040 $ $Date: 2010-09-28 09:18:31 +0200 (mar. 28 sept. 2010) $

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `private static class` | `EigenDecompositionImpl.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 double[]` | `imagEigenvalues` Imaginary part of the realEigenvalues.
    `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
    `EigenDecompositionImpl(double[] main, double[] secondary, double splitTolerance)` Calculates the eigen decomposition of the symmetric tridiagonal matrix.
    `EigenDecompositionImpl(RealMatrix matrix, double splitTolerance)` Calculates the eigen decomposition of the given symmetric matrix.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `private void` | `findEigenVectors(double[][] householderMatrix)` Find eigenvalues and eigenvectors (Dubrulle et al., 1971)
    `RealMatrix` | `getD()` Returns the block diagonal matrix D of the decomposition.
    `double` | `getDeterminant()` Return the determinant of the matrix
    `RealVector` | `getEigenvector(int i)` Returns a copy of the ith eigenvector of the original matrix.
    `double` | `getImagEigenvalue(int i)` Returns the imaginary part of the ith eigenvalue of the original matrix.
    `double[]` | `getImagEigenvalues()` Returns 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()` Returns a copy of the real parts of the eigenvalues of the original matrix.
    `DecompositionSolver` | `getSolver()` Get a solver for finding the A × X = B solution in exact linear sense.
    `RealMatrix` | `getV()` Returns the matrix V of the decomposition.
    `RealMatrix` | `getVT()` Returns the transpose of the matrix V of the decomposition.
    `private boolean` | `isSymmetric(RealMatrix matrix)` Check if a matrix is symmetric.
    `private void` | `transformToTridiagonal(RealMatrix matrix)` Transform matrix to tridiagonal.

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

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

- - ### Field Detail

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

  - ### Constructor Detail

    - #### EigenDecompositionImpl

          public EigenDecompositionImpl(RealMatrix matrix,
                                double splitTolerance)
                                 throws InvalidMatrixException

      Calculates the eigen decomposition of the given symmetric matrix.
      Parameters:
        `matrix` - The symmetric matrix to decompose.
        `splitTolerance` - dummy parameter, present for backward compatibility only.
      Throws:
        `InvalidMatrixException` - (wrapping a `ConvergenceException` if algorithm fails to converge

    - #### EigenDecompositionImpl

          public EigenDecompositionImpl(double[] main,
                                double[] secondary,
                                double splitTolerance)
                                 throws InvalidMatrixException

      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 triadiagonal form
        `secondary` - Secondary of the tridiagonal form
        `splitTolerance` - dummy parameter, present for backward compatibility only.
      Throws:
        `InvalidMatrixException` - (wrapping a `ConvergenceException` if algorithm fails to converge

  - ### Method Detail

    - #### isSymmetric

          private boolean isSymmetric(RealMatrix matrix)

      Check if a matrix is symmetric.
      Parameters:
        `matrix` - matrix to check
      Returns:
        true if matrix is symmetric

    - #### getV

          public RealMatrix getV()
                          throws InvalidMatrixException

      Returns 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).

      Specified by:
        `getV` in interface `EigenDecomposition`
      Returns:
        the V matrix
      Throws:
        `InvalidMatrixException`

    - #### getD

          public RealMatrix getD()
                          throws InvalidMatrixException

      Returns 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} }.

      Specified by:
        `getD` in interface `EigenDecomposition`
      Returns:
        the D matrix
      Throws:
        `InvalidMatrixException`
      See Also:
        `EigenDecomposition.getRealEigenvalues()`, `EigenDecomposition.getImagEigenvalues()`

    - #### getVT

          public RealMatrix getVT()
                           throws InvalidMatrixException

      Returns 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).

      Specified by:
        `getVT` in interface `EigenDecomposition`
      Returns:
        the transpose of the V matrix
      Throws:
        `InvalidMatrixException`

    - #### getRealEigenvalues

          public double[] getRealEigenvalues()
                                      throws InvalidMatrixException

      Returns a copy of the real parts of the eigenvalues of the original matrix.
      Specified by:
        `getRealEigenvalues` in interface `EigenDecomposition`
      Returns:
        a copy of the real parts of the eigenvalues of the original matrix
      Throws:
        `InvalidMatrixException`
      See Also:
        `EigenDecomposition.getD()`, `EigenDecomposition.getRealEigenvalue(int)`, `EigenDecomposition.getImagEigenvalues()`

    - #### getRealEigenvalue

          public double getRealEigenvalue(int i)
                                   throws InvalidMatrixException,
                                          ArrayIndexOutOfBoundsException

      Returns the real part of the ith eigenvalue of the original matrix.
      Specified by:
        `getRealEigenvalue` in interface `EigenDecomposition`
      Parameters:
        `i` - index of the eigenvalue (counting from 0)
      Returns:
        real part of the ith eigenvalue of the original matrix
      Throws:
        `InvalidMatrixException`
        `ArrayIndexOutOfBoundsException`
      See Also:
        `EigenDecomposition.getD()`, `EigenDecomposition.getRealEigenvalues()`, `EigenDecomposition.getImagEigenvalue(int)`

    - #### getImagEigenvalues

          public double[] getImagEigenvalues()
                                      throws InvalidMatrixException

      Returns a copy of the imaginary parts of the eigenvalues of the original matrix.
      Specified by:
        `getImagEigenvalues` in interface `EigenDecomposition`
      Returns:
        a copy of the imaginary parts of the eigenvalues of the original matrix
      Throws:
        `InvalidMatrixException`
      See Also:
        `EigenDecomposition.getD()`, `EigenDecomposition.getImagEigenvalue(int)`, `EigenDecomposition.getRealEigenvalues()`

    - #### getImagEigenvalue

          public double getImagEigenvalue(int i)
                                   throws InvalidMatrixException,
                                          ArrayIndexOutOfBoundsException

      Returns the imaginary part of the ith eigenvalue of the original matrix.
      Specified by:
        `getImagEigenvalue` in interface `EigenDecomposition`
      Parameters:
        `i` - index of the eigenvalue (counting from 0)
      Returns:
        imaginary part of the ith eigenvalue of the original matrix
      Throws:
        `InvalidMatrixException`
        `ArrayIndexOutOfBoundsException`
      See Also:
        `EigenDecomposition.getD()`, `EigenDecomposition.getImagEigenvalues()`, `EigenDecomposition.getRealEigenvalue(int)`

    - #### getEigenvector

          public RealVector getEigenvector(int i)
                                    throws InvalidMatrixException,
                                           ArrayIndexOutOfBoundsException

      Returns a copy of the ith eigenvector of the original matrix.
      Specified by:
        `getEigenvector` in interface `EigenDecomposition`
      Parameters:
        `i` - index of the eigenvector (counting from 0)
      Returns:
        copy of the ith eigenvector of the original matrix
      Throws:
        `InvalidMatrixException`
        `ArrayIndexOutOfBoundsException`
      See Also:
        `EigenDecomposition.getD()`

    - #### getDeterminant

          public double getDeterminant()

      Return the determinant of the matrix
      Specified by:
        `getDeterminant` in interface `EigenDecomposition`
      Returns:
        determinant of the matrix

    - #### getSolver

          public DecompositionSolver getSolver()

      Get a solver for finding the A × X = B solution in exact linear sense.
      Specified by:
        `getSolver` in interface `EigenDecomposition`
      Returns:
        a solver

    - #### transformToTridiagonal

          private void transformToTridiagonal(RealMatrix matrix)

      Transform matrix to tridiagonal.
      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 tri-diagonal form.

Copyright (c) 2003-2013 Apache Software Foundation