org.apache.commons.math.linear
Class EigenDecompositionImpl

java.lang.Object
  extended by org.apache.commons.math.linear.EigenDecompositionImpl
All Implemented Interfaces:
EigenDecomposition

public class EigenDecompositionImpl
extends java.lang.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
private static class EigenDecompositionImpl.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
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
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,
                                java.lang.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
java.lang.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,
                                java.lang.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
java.lang.ArrayIndexOutOfBoundsException
See Also:
EigenDecomposition.getD(), EigenDecomposition.getImagEigenvalues(), EigenDecomposition.getRealEigenvalue(int)

getEigenvector

public RealVector getEigenvector(int i)
                          throws InvalidMatrixException,
                                 java.lang.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
java.lang.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