toeplitz_cholesky

toeplitz_cholesky, a MATLAB code which computes the Cholesky factorization of a symmetric positive definite (SPD) Toeplitz matrix.

A Toeplitz matrix is a matrix which is constant along all diagonals. A schematic of a 3x4 Toeplitz matrix would be

        a  b  c  d
        e  a  b  c
        f  e  a  b
      

A symmetric matrix is a matrix with N rows and N columns, such that A(I,J) = A(J,I) for all indices I and J. All the eigenvalues of a symmetric matrix are real.

A symmetric Toeplitz matrix is a matrix which is symmetric and Toeplitz. A schematic of a 4x4 symmetric Toeplitz matrix would be

        a  b  c  d
        b  a  b  c
        c  b  a  b
        d  c  b  a
      

A nonnegative definite symmetric matrix A is a symmetric matrix whose eigenvalues are all nonnegative.

Given a nonnegative definite symmetric matrix A, the upper Cholesky factor R is an upper triangular matrix such that A = R' * R; the lower Cholesky factor L is a lower triangular matrix such that A = L L'. Obviously, L = R'.

A Toeplitz matrix can be represented in a compressed format that stores the first row and the first column (omitting the first entry). One convenient format would be to create the 2xN array G as follows:

       G(1,1:N) = A(1,1:N)
       G(2,1)   = 0.0
       G(2,2:N) = A(2:N,1)
      

A symmetric Toeplitz matrix can be represented in a compressed format that stores just the first row.

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

toeplitz_cholesky is available in a C version and a C++ version and a Fortran77 version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

toeplitz_cholesky_test

asa006, a MATLAB code which computes the Cholesky factorization of a symmetric positive definite (SPD) matrix, by Michael Healy.

hankel_cholesky, a MATLAB code which computes the upper Cholesky factor R of a symmetric positive definite (SPD) Hankel matrix H so that H = R' * R.

Reference:

1. Michael Stewart,
   Cholesky factorization of semi-definite Toeplitz matrices,
   Linear Algebra and its Applications,
   Volume 254, pages 497-525, 1997.

Source Code:

• r8mat_print.m, prints an R8MAT.
• r8mat_print_some.m, prints some of an R8MAT.
• r8vec_print.m, prints an R8VEC.
• t_cholesky_lower.m, given the first row of a Toeplitz matrix, computes the lower Cholesky factor.
• t_cholesky_upper.m, given the first row of a Toeplitz matrix, computes the upper Cholesky factor.
• toep_cholesky_lower.m, given a compressed Toeplitz matrix, computes the lower Cholesky factor.
• toep_cholesky_upper.m, given a compressed Toeplitz matrix, computes the upper Cholesky factor.
• toeplitz_cholesky_lower.m, given a Toeplitz matrix, computes the lower Cholesky factor.
• toeplitz_cholesky_upper.m, given a Toeplitz matrix, computes the upper Cholesky factor.