MATLAB^®

chol - Cholesky factorization

Syntax

R = chol(A) L = chol(A,'lower') [R,p] = chol(A) [L,p] = chol(A,'lower') [R,p,S] = chol(A) [R,p,s] = chol(A,'vector') [L,p,s] = chol(A,'lower','vector')

Description

R = chol(A) produces an upper triangular matrix R from the diagonal and upper triangle of matrix A, satisfying the equation R'*R=A. The lower triangle is assumed to be the (complex conjugate) transpose of the upper triangle. Matrix A must be positive definite; otherwise, MATLAB software displays an error message.

L = chol(A,'lower') produces a lower triangular matrix L from the diagonal and lower triangle of matrix A, satisfying the equation L*L'=A. When A is sparse, this syntax of chol is typically faster. Matrix A must be positive definite; otherwise MATLAB displays an error message.

[R,p] = chol(A) for positive definite A, produces an upper triangular matrix R from the diagonal and upper triangle of matrix A, satisfying the equation R'*R=A and p is zero. If A is not positive definite, then p is a positive integer and MATLAB does not generate an error. When A is full, R is an upper triangular matrix of order q=p-1 such that R'*R=A(1:q,1:q). When A is sparse, R is an upper triangular matrix of size q-by-n so that the L-shaped region of the first q rows and first q columns of R'*R agree with those of A.

[L,p] = chol(A,'lower') for positive definite A, produces a lower triangular matrix L from the diagonal and lower triangle of matrix A, satisfying the equation L*L'=A and p is zero. If A is not positive definite, then p is a positive integer and MATLAB does not generate an error. When A is full, L is a lower triangular matrix of order q=p-1 such that L*L'=A(1:q,1:q). When A is sparse, L is a lower triangular matrix of size q-by-n so that the L-shaped region of the first q rows and first q columns of L*L' agree with those of A.

[R,p,S] = chol(A), when A is sparse, returns a permutation matrix S. Note that the preordering S may differ from that obtained from amd since chol will slightly change the ordering for increased performance. When p=0, R is an upper triangular matrix such that R'*R=S'*A*S. When p is not zero, R is an upper triangular matrix of size q-by-n so that the L-shaped region of the first q rows and first q columns of R'*R agree with those of S'*A*S. The factor of S'*A*S tends to be sparser than the factor of A.

[R,p,s] = chol(A,'vector') returns the permutation information as a vector s such that A(s,s)=R'*R, when p=0. You can use the 'matrix' option in place of 'vector' to obtain the default behavior.

[L,p,s] = chol(A,'lower','vector') uses only the diagonal and the lower triangle of A and returns a lower triangular matrix L and a permutation vector s such that A(s,s)=L*L', when p=0. As above, you can use the 'matrix' option in place of 'vector' to obtain a permutation matrix.

For sparse A, CHOLMOD is used to compute the Cholesky factor.

Note Using chol is preferable to using eig for determining positive definiteness.

Examples

Example 1

The gallery function provides several symmetric, positive, definite matrices.

A=gallery('moler',5)

A =

     1    -1    -1    -1    -1
    -1     2     0     0     0
    -1     0     3     1     1
    -1     0     1     4     2
    -1     0     1     2     5

C=chol(A)

ans =

     1    -1    -1    -1    -1
     0     1    -1    -1    -1
     0     0     1    -1    -1
     0     0     0     1    -1
     0     0     0     0     1
isequal(C'*C,A)

ans =

     1

For sparse input matrices, chol returns the Cholesky factor.

N = 100;
A = gallery('poisson', N);

N represents the number of grid points in one direction of a square N-by-N grid. Therefore, A is by .

L = chol(A, 'lower');
D = norm(A - L*L', 'fro');

The value of D will vary somewhat among different versions of MATLAB but will be on order of .

Example 2

The binomial coefficients arranged in a symmetric array create a positive definite matrix.

n = 5;
X = pascal(n)
X =
    1    1    1    1    1
    1    2    3    4    5
    1    3    6   10   15
    1    4   10   20   35
    1    5   15   35   70

This matrix is interesting because its Cholesky factor consists of the same coefficients, arranged in an upper triangular matrix.

R = chol(X)
R =
    1    1    1    1    1
    0    1    2    3    4
    0    0    1    3    6
    0    0    0    1    4
    0    0    0    0    1

Destroy the positive definiteness (and actually make the matrix singular) by subtracting 1 from the last element.

X(n,n) = X(n,n)-1

X =
    1    1    1    1    1
    1    2    3    4    5
    1    3    6   10   15
    1    4   10   20   35
    1    5   15   35   69

Now an attempt to find the Cholesky factorization of X fails.

chol(X)
??? Error using ==> chol
Matrix must be positive definite.

Algorithm

For full matrices X, chol uses the LAPACK routines listed in the following table.

	Real	Complex
`X` `double`	DPOTRF	ZPOTRF
`X` `single`	SPOTRF	CPOTRF

For sparse matrices, MATLAB software uses CHOLMOD to compute the Cholesky factor.

References

[1] Anderson, E., Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK User's Guide (http://www.netlib.org/lapack/lug/lapack_lug.html), Third Edition, SIAM, Philadelphia, 1999.

[2] Davis, T. A., CHOLMOD Version 1.0 User Guide (http://www.cise.ufl.edu/research/sparse/cholmod), Dept. of Computer and Information Science and Engineering, Univ. of Florida, Gainesville, FL, 2005.