de.lmu.ifi.dbs.elki.math.linearalgebra

Class EigenvalueDecomposition

java.lang.Object

de.lmu.ifi.dbs.elki.math.linearalgebra.EigenvalueDecomposition

public class EigenvalueDecomposition
extends java.lang.Object

Eigenvalues and eigenvectors of a real matrix.

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.times(D.timesTranspose(V)) and V.timesTranspose(V) 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.times(V) equals V.times(D). The matrix V may be badly conditioned, or even singular, so the validity of the equation A = V*D*inverse(V) depends upon V.cond().

Since:

0.1

Author:

Arthur Zimek

Field Summary

Fields

Modifier and Type	Field and Description
private double[]	d Arrays for internal storage of eigenvalues.
private double[]	e Arrays for internal storage of eigenvalues.
private double[][]	H Array for internal storage of nonsymmetric Hessenberg form.
private int	n Row and column dimension (square matrix).
private double[]	ort Working storage for nonsymmetric algorithm.
private double[][]	V Array for internal storage of eigenvectors.

Constructor Summary

Constructors

Constructor and Description
EigenvalueDecomposition(double[][] A) Check for symmetry, then construct the eigenvalue decomposition

Method Summary

Modifier and Type	Method and Description
private static void	cdiv(double xr, double xi, double yr, double yi, double[] buf, int off) Complex scalar division, writing into buf[off++]
double[][]	getD() Return the block diagonal eigenvalue matrix
double[]	getImagEigenvalues() Return the imaginary parts of the eigenvalues
double[]	getRealEigenvalues() Return the real parts of the eigenvalues
double[][]	getV() Return the eigenvector matrix
private void	hqr2() Nonsymmetric reduction from Hessenberg to real Schur form.
private void	hqr2BacksubstituteComplex(int n, double p, double q, double norm)
private void	hqr2BacksubstituteReal(int n, double p, double norm)
private void	hqr2BackTransformation(int nn, int low, int high) Back transformation to get eigenvectors of original matrix.
private static void	modifyQP(double[] Hi, int n, double p, double q)
private static void	modifyQR(double[] Hi, int k, boolean notlast, double q, double r, double x, double y, double z)
private void	orthes() Nonsymmetric reduction to Hessenberg form.
private void	sortEigen()
private void	tql2() Symmetric tridiagonal QL algorithm.
private double	tql2ComputeImplicitShift(int l)
private void	tql2ImplicitQL(int l, int m, double dl1)
private void	tred2() Symmetric Householder reduction to tridiagonal form.
private void	tred2AccumulateTransformations()

Methods inherited from class java.lang.Object

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

Field Detail

n

private final int n

Row and column dimension (square matrix).

d

private double[] d

Arrays for internal storage of eigenvalues.

e

private double[] e

Arrays for internal storage of eigenvalues.

V

private double[][] V

Array for internal storage of eigenvectors.

H

private double[][] H

Array for internal storage of nonsymmetric Hessenberg form.

ort

private double[] ort

Working storage for nonsymmetric algorithm.

Constructor Detail

EigenvalueDecomposition

public EigenvalueDecomposition(double[][] A)

Check for symmetry, then construct the eigenvalue decomposition

Parameters:

A - Square matrix

Method Detail

tred2

private void tred2()

Symmetric Householder reduction to tridiagonal form.

tred2AccumulateTransformations

private void tred2AccumulateTransformations()

tql2

private void tql2()

Symmetric tridiagonal QL algorithm.

tql2ComputeImplicitShift

private double tql2ComputeImplicitShift(int l)

tql2ImplicitQL

private void tql2ImplicitQL(int l,
                            int m,
                            double dl1)

sortEigen

private void sortEigen()

orthes

private void orthes()

Nonsymmetric reduction to Hessenberg form.

cdiv

private static void cdiv(double xr,
                         double xi,
                         double yr,
                         double yi,
                         double[] buf,
                         int off)

Complex scalar division, writing into buf[off++]

hqr2

private void hqr2()

Nonsymmetric reduction from Hessenberg to real Schur form.

modifyQP

private static void modifyQP(double[] Hi,
                             int n,
                             double p,
                             double q)

modifyQR

private static void modifyQR(double[] Hi,
                             int k,
                             boolean notlast,
                             double q,
                             double r,
                             double x,
                             double y,
                             double z)

hqr2BacksubstituteReal

private void hqr2BacksubstituteReal(int n,
                                    double p,
                                    double norm)

hqr2BacksubstituteComplex

private void hqr2BacksubstituteComplex(int n,
                                       double p,
                                       double q,
                                       double norm)

hqr2BackTransformation

private void hqr2BackTransformation(int nn,
                                    int low,
                                    int high)

Back transformation to get eigenvectors of original matrix.

getV

public double[][] getV()

Return the eigenvector matrix

Returns:

V

getRealEigenvalues

public double[] getRealEigenvalues()

Return the real parts of the eigenvalues

Returns:

real(diag(D))

getImagEigenvalues

public double[] getImagEigenvalues()

Return the imaginary parts of the eigenvalues

Returns:

imag(diag(D))

getD

public double[][] getD()

Return the block diagonal eigenvalue matrix

Returns:

D