cholesky -- computes the Cholesky decomposition of a positive semidefinite matrix

Synopsis

Usage:

cholesky A
Inputs:
- A, an $n\times n$ PSD matrix
Optional inputs:
- Tolerance => ..., default value .000001
Outputs:
- L, a matrix, a lower-triangular matrix, with $A = LL^T$

Description

This method computes the Cholesky decomposition of a symmetric positive semidefinite matrix $A$, which is a factorization $A = LL^T$, where $L$ is lower-triangular. If $A$ is not positive-definite, then the Cholesky decomposition is not unique - in this case, this method will attempt to give an output which is as sparse as possible.

When working over an InexactFieldFamily like RR or CC, the option Tolerance can be used to specify the internal threshold for checking equality (any floating point number below the tolerance is treated as numerically zero).

i1 : A = randomPSD 5 -- 5x5 PSD of full rank

o1 = | .585298   -.0545901 .0184505  -.0599728  -.149145   |
     | -.0545901 .761001   -.0118983 -.160458   -.02979    |
     | .0184505  -.0118983 .56512    .0605255   -.0250409  |
     | -.0599728 -.160458  .0605255  .609506    -.00367036 |
     | -.149145  -.02979   -.0250409 -.00367036 .761799    |

                5         5
o1 : Matrix RR    <-- RR
              53        53

i2 : L = cholesky A

o2 = | .765048   0         0         0         0      |
     | -.0713552 .869431   0         0         0      |
     | .0241168  -.0117059 .751266   0         0      |
     | -.078391  -.190989  .0801052  .748643   0      |
     | -.194949  -.0502634 -.0278566 -.0351581 .84809 |

                5         5
o2 : Matrix RR    <-- RR
              53        53

i3 : clean(1e-12, A - L*transpose L) == 0

o3 = true

i4 : B = randomPSD(7, 3) -- 7x7 PSD matrix of rank 3

o4 = | .174021  .0402662  .192987  .117982   .118213   -.124471  .0219834  |
     | .0402662 .211585   .0846263 .192158   -.224018  .0837642  -.0805872 |
     | .192987  .0846263  .222408  .159648   .0747663  -.128752  .0127036  |
     | .117982  .192158   .159648  .243413   -.0734574 .107218   -.0954143 |
     | .118213  -.224018  .0747663 -.0734574 .483189   -.0482137 .0499495  |
     | -.124471 .0837642  -.128752 .107218   -.0482137 .494878   -.202561  |
     | .0219834 -.0805872 .0127036 -.0954143 .0499495  -.202561  .0954897  |

                7         7
o4 : Matrix RR    <-- RR
              53        53

i5 : L = cholesky B

o5 = | .417158  0        0        0 0 0 0 |
     | .096525  .449742  0        0 0 0 0 |
     | .462623  .0888769 .0221228 0 0 0 0 |
     | .282823  .366563  -.170457 0 0 0 0 |
     | .283377  -.558922 -.300821 0 0 0 0 |
     | -.298379 .250289  -.585836 0 0 0 0 |
     | .052698  -.190496 .237537  0 0 0 0 |

                7         7
o5 : Matrix RR    <-- RR
              53        53

i6 : clean(1e-12, B - L*transpose L) == 0

o6 = true

Ways to use cholesky :

cholesky(Matrix)

For the programmer

The object cholesky is a method function with options.