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 × V^T. 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)

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 i^th eigenvalue of the original matrix.

Parameters:

i - index of the eigenvalue (counting from 0)

Returns:

real part of the i^th 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 i^th eigenvalue of the original matrix.

Parameters:

i - Index of the eigenvalue (counting from 0).

Returns:

the imaginary part of the i^th eigenvalue of the original matrix.

See Also:

getD(), getImagEigenvalues(), getRealEigenvalue(int)

getEigenvector

public RealVector getEigenvector(int i)

Gets a copy of the i^th eigenvector of the original matrix.

Parameters:

i - Index of the eigenvector (counting from 0).

Returns:

a copy of the i^th 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 positive 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