IMSL C# Numerical Library

Cholesky Class

Cholesky factorization of a matrix of type double.

For a list of all members of this type, see Cholesky Members.

System.Object
   Imsl.Math.Cholesky

public class Cholesky

Thread Safety

Public static (Shared in Visual Basic) members of this type are safe for multithreaded operations. Instance members are not guaranteed to be thread-safe.

Remarks

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_N\ldots G_1of 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= \cos\theta _i, s_i= \sin\theta_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 U\left[ \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
.

Requirements

Namespace: Imsl.Math

Assembly: ImslCS (in ImslCS.dll)

See Also

Cholesky Members | Imsl.Math Namespace | Example