Cholesky (JMSL Numerical Library)

Overview

Package

Class

Tree

Index

Help

JMSL^TM Numerical Library 6.1

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.imsl.math
Class Cholesky

java.lang.Object
  com.imsl.math.Cholesky

All Implemented Interfaces:: Serializable, Cloneable

public class Cholesky
extends Object
implements Serializable, Cloneable
extends Object
implements Serializable, Cloneable

Cholesky factorization of a matrix of type double.

Class Cholesky uses the Cholesky-Banachiewicz algortithm to factor the matrix A.

The Cholesky factorization of a matrix is , where R is a lower triangular matrix. Thus,

$A = RR^T = begin{pmatrix} R_{11} & 0 & 0\ R_{21} & R_{22} & 0\ R_{31} & R_{32} & R_{33} end{pmatrix} begin{pmatrix} R_{11} & R_{21} & R_{31}\ 0 & R_{22} & R_{32}\ 0 & 0 & R_{33} end{pmatrix} = begin{pmatrix} R^2_{11} & & (Symmetric) \ R_{21}R_{11} & R^2_{22}+R^2_{22} & \ R_{31}R_{11} & R_{31}R_{21}+R_{32}R_{22} & R^2_{31}+R^2_{32}+R^2_{33} end{pmatrix}$

which leads to the following for the entries of the lower triangular marix R:

$R_{i,j} = frac{1}{R_{j,j}}left ( A_{i,j}-sum_{k=1}^{j-1}R_{i,k}R_{j,k} right )mbox{,} ,,,, mbox{for},,, i>j$

and

$R_{i,i} = sqrt{A_{i,i} - sum_{k=1}^{i-1}R_{i,k}^2} ,,,mbox{.}$

The method update is based on the LINPACK routine SCHUD; see Dongarra et al. (1979) and updates the Cholesky factorization of the real symmetric positive definite matrix A after a rank-one matrix is added. Given this factorization, update computes the factorization such that

$A + xx^T = tilde R tilde R^T ,, mbox{.}$

Similarly, the method downdate, based on the LINPACK routine SCHDD; see Dongarra et al. (1979), downdates the

Cholesky factorization of the real symmetric positive definite matrix A after a rank-one matrix is subtracted. downdate computes the factorization

such that

$A - xx^T = tilde R tilde R^T ,, mbox{.}$

This is not always possible, since

may not be positive definite.

downdate determines an orthogonal matrix U as the product of Givens rotations, such that

$U left[ begin{array}{l} R^T \ 0 \ end{array} right] = left[ begin{array}{l} {tilde R}^T \ x^T \ end{array} right]$

By multiplying this equation by its transpose and noting that , the desired result

is obtained.

Let a be the solution of the linear system and let

$alpha = sqrt {1 - left| a right|_2^2 }$

The Givens rotations, , are chosen such that

$G_1 cdots G_N left[ begin{array}{l}a \ alpha end{array} right] = left[ begin{array}{l} 0 \ 1 end{array} right]$

The , are (N + 1) by (N + 1) matrices of the form

$G_i = left[ {begin{array}{*{20}c}{ I_{i - 1} } & 0 & 0 & 0 \ 0 & {c_i } & 0 & { - s_i } \ 0 & 0 & {I_{N - i} } & 0 \ 0 & {s_i } & 0 & {c_i } \ end{array}} right]$

where

is the identity matrix of order k; and

for some

The Givens rotations are then used to form

${tilde R}^T,,,G_1 cdots ,G_N left[ begin{array}{l} R^T \ 0 \ end{array} right] = left[ begin{array}{l} {tilde R}^T \ {tilde x^T} \ end{array} right]$

The matrix

is lower triangular and

because

$x = left( {R ,,, 0} right) left[ begin{array}{l}a \ alpha \ end{array} right] = left( R ,,, 0 right) U^TU left[ begin{array}{l}a \ alpha \ end{array} right] = left( {tilde R ,,, tilde x} right) left[ begin{array}{l}0 \ 1 \ end{array} right] = tilde x$

See Also:: Example, Serialized Form

Nested Class Summary
`static class`	`Cholesky.NotSPDException` The matrix is not symmetric, positive definite.

Constructor Summary
`Cholesky(double[][] a)` Create the Cholesky factorization of a symmetric positive definite matrix of type `double`.

Method Summary
`void`	`downdate(double[] x)` Downdates the factorization by subtracting a rank-1 matrix.
`double[][]`	`getR()` Returns the R matrix that results from the Cholesky factorization.
`double[][]`	`inverse()` Returns the inverse of this matrix
`double[]`	`solve(double[] b)` Solve Ax = b where A is a positive definite matrix with elements of type `double`.
`void`	`update(double[] x)` Updates the factorization by adding a rank-1 matrix.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

Cholesky

public Cholesky(double[][] a)
         throws SingularMatrixException,
                Cholesky.NotSPDException

Create the Cholesky factorization of a symmetric positive definite matrix of type double.

Parameters:: a - a double square matrix to be factored
Throws:: IllegalArgumentException - Thrown when the row lengths of matrix a are not equal (for example, the matrix edges are "jagged".); SingularMatrixException - Thrown when the input matrix A is singular.; Cholesky.NotSPDException - Thrown when the input matrix is not symmetric, positive definite.

Method Detail

downdate

public void downdate(double[] x)
              throws Cholesky.NotSPDException

Downdates the factorization by subtracting a rank-1 matrix. The object will contain the Cholesky factorization of

, where A is the previously factored matrix.

Parameters:: x - A double array which specifies the rank-1 matrix. x is not modified by this function.
Throws:: Cholesky.NotSPDException - if is not symmetric positive-definite.

getR

public double[][] getR()

Returns the R matrix that results from the Cholesky factorization.

Returns:: a double matrix which contains the lower triangular R matrix that results from the Cholesky factorization such that

inverse

public double[][] inverse()

Returns the inverse of this matrix

Returns:: a double matrix containing the inverse

solve

public double[] solve(double[] b)

Solve Ax = b where A is a positive definite matrix with elements of type double.

Parameters:: b - a double array containing the right-hand side of the linear system
Returns:: a double array containing the solution to the system of linear equations

update

public void update(double[] x)

Updates the factorization by adding a rank-1 matrix. The object will contain the Cholesky factorization of