edu.udo.cs.myRVM.Util
Class SECholeskyDecomposition

java.lang.Object
  edu.udo.cs.myRVM.Util.SECholeskyDecomposition

public class SECholeskyDecomposition
extends java.lang.Object

A modified cholesky factorization. Given a n x n matrix A this decomposition produces a matrix L, such that L * L' = A + E, with E being a minimal diagonal matrix making the sum of both matrices positive definite (and regular). In contrast to the standard cholesky decomposition (as implemented in e.g. Jama) the matrix A doesn't have to be regular and positive definite as often happens due to numerical instabilities. The determination of the diagonal elements of E is based on Gerschgorin's circle theorem minimizing ||E||_inf. The a-priori upper bound of ||E||_inf is linear in n; REFERENCES: Robert B. Schnabel and Elizabeth Eskow. 1990. "A New Modified Cholesky Factorization," SIAM Journal of Scientific Statistical Computating, 11, 6: 1136-58. Robert B. Schnabel and Elizabeth Eskow. 1999. "A revised modified Cholesky factorization algorithm," SIAM J. Optim., 9, 4: 1135--1148 (electronic) Jeff Gill and Gary King. 1998. "`Hessian not Invertable.' Help!" manuscript in progress, Harvard University.

Version:

$Id: SECholeskyDecomposition.java,v 1.5 2006/08/03 14:39:34 ingomierswa Exp $

Author:

Piotr Kasprzak

Nested Class Summary

private class

SECholeskyDecomposition.PivotTransform Data structures needed for the recording of the pivot transformations.

Field Summary

private double	detL
private Jama.Matrix	E
private double[]	E_Diagonal
private double	ENorm
private Jama.Matrix	L The L-factor (lower triangle matrix) of matrix factorization calculated in decompose().
private int	n
private java.util.LinkedList<SECholeskyDecomposition.PivotTransform>	pivotTransformQueue
private Jama.Matrix	PTR The matrix used to reverse the pivot-transformations used in decompose() to construct L (PTR = Pivot Transform Reverse): PTR * (L * L') * PTR' = A + E.

Constructor Summary

SECholeskyDecomposition(double[][] A)
Constructors.

SECholeskyDecomposition(Jama.Matrix A)

Method Summary

private void	buildPTR() Build the Pivot-Transform-Reverse matrix PTR.
private void	decompose(Jama.Matrix MA_orig) Do the hard work.
double	getDetA() Return the determinant of A.
double	getDetL() Return the determinant of L.
double[]	getE_Diagonal() Return the diagonal of error-matrix E with the pivoting still applied.
Jama.Matrix	getE() Return the error-matrix E with pivoting reversed.
double	getENorm() Return the infinity norm of matrix E.
Jama.Matrix	getL() Return the lower triangle matrix factor of the cholesky decomposition.
Jama.Matrix	getPTR() Return the matrix PTR with PTR * (L * L') * PTR' = A + E.
private void	swapRowsAndColumns(double[][] A, int i, int j, boolean isSymmetric, int offset) Swap rows i<->j and columns i<->j.

Methods inherited from class java.lang.Object

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

Field Detail

L

private Jama.Matrix L

The L-factor (lower triangle matrix) of matrix factorization calculated in decompose(). NOTE: Due to pivoting the rows and columns DO NOT MATCH with the original matrix A.

PTR

private Jama.Matrix PTR

The matrix used to reverse the pivot-transformations used in decompose() to construct L (PTR = Pivot Transform Reverse): PTR * (L * L') * PTR' = A + E. It's constructed from the reverse sequence of row/column swaps recorded in decompose().

pivotTransformQueue

private java.util.LinkedList<SECholeskyDecomposition.PivotTransform> pivotTransformQueue

E

private Jama.Matrix E

E_Diagonal

private double[] E_Diagonal

ENorm

private double ENorm

detL

private double detL

n

private int n

Constructor Detail

SECholeskyDecomposition

public SECholeskyDecomposition(double[][] A)

Constructors.

Parameters:

A -

SECholeskyDecomposition

public SECholeskyDecomposition(Jama.Matrix A)

Method Detail

swapRowsAndColumns

private void swapRowsAndColumns(double[][] A,
                                int i,
                                int j,
                                boolean isSymmetric,
                                int offset)

Swap rows i<->j and columns i<->j.

Parameters:

A -

i -

j -

decompose

private void decompose(Jama.Matrix MA_orig)

Do the hard work.

Parameters:

MA_orig -

buildPTR

private void buildPTR()

Build the Pivot-Transform-Reverse matrix PTR. We start with a n x n identity matrix and for each recorded pivot transformation swap the according rows, reversing the sequence and starting with the last pivot transformation.

getL

public Jama.Matrix getL()

Return the lower triangle matrix factor of the cholesky decomposition.

getPTR

public Jama.Matrix getPTR()

Return the matrix PTR with PTR * (L * L') * PTR' = A + E.

getE_Diagonal

public double[] getE_Diagonal()

Return the diagonal of error-matrix E with the pivoting still applied.

getE

public Jama.Matrix getE()

Return the error-matrix E with pivoting reversed.

getENorm

public double getENorm()

Return the infinity norm of matrix E.

getDetL

public double getDetL()

Return the determinant of L.

getDetA

public double getDetA()

Return the determinant of A.