JMSLTM Numerical Library 5.0.1

com.imsl.math
Class Cholesky

java.lang.Object
  extended by 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 is based on the LINPACK routine SCHDC; see Dongarra et al. (1979).

Before the decomposition is computed, initial elements are moved to the leading part of A and final elements to the trailing part of A. During the decomposition only rows and columns corresponding to the free elements are moved. The result of the decomposition is an upper triangular matrix R and a permutation matrix P that satisfy P^T AP = R^T R, where P is represented by ipvt.

The method update is based on the LINPACK routine SCHUD; see Dongarra et al. (1979).

The Cholesky factorization of a matrix is A = R^T R, where R is an upper triangular matrix. Given this factorization, downdate computes the factorization

A - xx^T  = tilde R^T tilde R

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

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

By multiplying this equation by its transpose and noting that U^T U = I, the desired result

R^T R - xx^T  = tilde R^T tilde R

is obtained.

Let a be the solution of the linear system R^T  a = x and let

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

The Givens rotations, G_i, 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 G_i, are (N + 1) * (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 I_k is the identity matrix of order k; and c_i= costheta _i, s_i= sintheta_i for some theta_i.

The Givens rotations are then used to form

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

The matrix

tilde R

is upper triangular and

tilde x = x

because

x = left( {R^T 0} right)
          left[ begin{array}{l}a \ alpha  \ end{array} right] =
          left( R^T 0 right)
          U^T Uleft[ begin{array}{l}a \ alpha  \  end{array} right] = 
          left( {tilde R^T 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 a - x times x^T, 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 a - x times x^T is not symmetric positive-definite.

getR

public double[][] getR()
Returns the R matrix that results from the Cholesky factorization. R is a lower triangular matrix and A = RR^T.

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

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 a + x*X^T = b, 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.

JMSLTM Numerical Library 5.0.1

Copyright © 1970-2008 Visual Numerics, Inc.
Built July 8 2008.