Cholesky (JMSL Numerical Library)

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

All Implemented Interfaces:

Serializable, Cloneable
```
public class Cholesky
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

Nested Classes
Modifier and Type Class and Description

static class Cholesky.NotSPDException
The matrix is not symmetric, positive definite.

Nested Classes
Modifier and Type	Class and Description
`static class`	`Cholesky.NotSPDException` The matrix is not symmetric, positive definite.

Constructor Summary

Constructors
Constructor and Description

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

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

Method Summary

Methods
Modifier and Type	Method and Description
`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 , 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.

Class Cholesky

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

Cholesky

Method Detail

downdate

getR

inverse

solve

update