org.apache.commons.math3.linear
Class EigenDecomposition

java.lang.Object
  extended by org.apache.commons.math3.linear.EigenDecomposition

public class EigenDecomposition
extends Object

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.

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

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 (changed to concrete class in 3.0)
Version:
$Id: EigenDecomposition.java 1244107 2012-02-14 16:17:55Z erans $
See Also:
MathWorld, Wikipedia

Nested Class Summary
private static class EigenDecomposition.Solver
          Specialized solver.
 
Field Summary
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
EigenDecomposition(double[] main, double[] secondary, double splitTolerance)
          Calculates the eigen decomposition of the symmetric tridiagonal matrix.
EigenDecomposition(RealMatrix matrix, double splitTolerance)
          Calculates the eigen decomposition of the given symmetric matrix.
 
Method Summary
private  void findEigenVectors(double[][] householderMatrix)
          Find eigenvalues and eigenvectors (Dubrulle et al., 1971)
 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 getV()
          Gets the matrix V of the decomposition.
 RealMatrix getVT()
          Gets the transpose of the matrix V of the decomposition.
private  boolean isSymmetric(RealMatrix matrix, boolean raiseException)
          Check if a matrix is symmetric.
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

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

EigenDecomposition

public EigenDecomposition(RealMatrix matrix,
                          double splitTolerance)
Calculates the eigen decomposition of the given symmetric matrix.

Parameters:
matrix - Matrix to decompose. It must be symmetric.
splitTolerance - Dummy parameter (present for backward compatibility only).
Throws:
NonSymmetricMatrixException - if the matrix is not symmetric.
MaxCountExceededException - if the algorithm fails to converge.

EigenDecomposition

public EigenDecomposition(double[] main,
                          double[] secondary,
                          double splitTolerance)
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

isSymmetric

private boolean isSymmetric(RealMatrix matrix,
                            boolean raiseException)
Check if a matrix is symmetric.

Parameters:
matrix - Matrix to check.
raiseException - If true, the method will throw an exception if matrix is not symmetric.
Returns:
true if matrix is symmetric.
Throws:
NonSymmetricMatrixException - if the matrix is not symmetric and raiseException is true.

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.

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.

getSolver

public DecompositionSolver getSolver()
Gets a solver for finding the A × X = B solution in exact linear sense.

Returns:
a solver.

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.


Copyright (c) 2003-2013 Apache Software Foundation