Inlinear algebra, theCholesky decomposition orCholesky factorization (pronounced/ʃəˈlɛski/shə-LES-kee) is adecomposition of aHermitian,positive-definite matrix into the product of alower triangular matrix and itsconjugate transpose, which is useful for efficient numerical solutions, e.g.,Monte Carlo simulations. It was discovered byAndré-Louis Cholesky for real matrices, and posthumously published in 1924.^[1]When it is applicable, the Cholesky decomposition is roughly twice as efficient as theLU decomposition for solvingsystems of linear equations.^[2]

The Cholesky decomposition of aHermitianpositive-definite matrixA is a decomposition of the form

$${\displaystyle \mathbf{A}={\mathbf{L}\mathbf{L}}^{\ast },}$$

whereL is alower triangular matrix with real and positive diagonal entries, andL* denotes theconjugate transpose ofL. Every Hermitian positive-definite matrix (and thus also every real symmetric positive-definite matrix) has a Cholesky decomposition and the lower triangular matrix is unique if we impose the diagonal to be strictly positive.^[3]

The converse holds trivially: ifA can be written asLL* for some invertibleL, lower triangular or otherwise, thenA is Hermitian and positive definite.

WhenA is a real matrix (hence symmetric positive-definite), the factorization may be written$${\displaystyle \mathbf{A}={\mathbf{L}\mathbf{L}}^{\mathsf{T}},}$$whereL is a real lower triangular matrix with positive diagonal entries.^[4][5][6]

If a Hermitian matrixA is only positive semidefinite, instead of positive definite, then it still has a decomposition of the formA =LL* where the diagonal entries ofL are allowed to be zero.^[7]The decomposition need not be unique, for example:for anyθ. However, if the rank ofA isr, then there is a unique lower triangularL with exactlyr positive diagonal elements andn −r columns containing all zeroes.^[8]

Alternatively, the decomposition can be made unique when a pivoting choice is fixed. Formally, ifA is ann ×n positive semidefinite matrix of rankr, then there is at least one permutation matrixP such thatP A P^T has a unique decomposition of the formP A P^T =L L^* with,whereL₁ is anr ×r lower triangular matrix with positive diagonal.^[9]

A closely related variant of the classical Cholesky decomposition is the LDL decomposition,

$${\displaystyle \mathbf{A}={\mathbf{L}\mathbf{D}\mathbf{L}}^{\ast },}$$

whereL is alower unit triangular (unitriangular) matrix, andD is adiagonal matrix. That is, the diagonal elements ofL are required to be 1 at the cost of introducing an additional diagonal matrixD in the decomposition. The main advantage is that the LDL decomposition can be computed and used with essentially the same algorithms, but avoids extracting square roots.^[10]

For this reason, the LDL decomposition is often called thesquare-root-free Cholesky decomposition. For real matrices, the factorization has the formA =LDL^T and is often referred to asLDLT decomposition (orLDL^T decomposition, orLDL′). It is reminiscent of theeigendecomposition of real symmetric matrices,A =QΛQ^T, but is quite different in practice becauseΛ andD are notsimilar matrices.

The LDL decomposition is related to the classical Cholesky decomposition of the formLL* as follows:

$${\displaystyle \mathbf{A}={\mathbf{L}\mathbf{D}\mathbf{L}}^{\ast }=\mathbf{L}{\mathbf{D}}^{1/2}{\left({\mathbf{D}}^{1/2}\right)}^{\ast }{\mathbf{L}}^{\ast }=\mathbf{L}{\mathbf{D}}^{1/2}{\left(\mathbf{L}{\mathbf{D}}^{1/2}\right)}^{\ast }.}$$

Conversely, given the classical Cholesky decomposition$\mathbf{A}=\mathbf{C}{\mathbf{C}}^{\ast }$ of a positive definite matrix, ifS is a diagonal matrix that contains themain diagonal of$\mathbf{C}$, thenA can be decomposed as$\mathbf{L}\mathbf{D}{\mathbf{L}}^{\ast }$ where$${\displaystyle \mathbf{L}=\mathbf{C}{\mathbf{S}}^{-1}}$$ (this rescales each column to make diagonal elements 1),$${\displaystyle \mathbf{D}=\mathbf{S}{\mathbf{S}}^{\ast }.}$$

IfA is positive definite then the diagonal elements ofD are all positive.For positive semidefiniteA, an$\mathbf{L}\mathbf{D}{\mathbf{L}}^{\ast }$ decomposition exists where the number of non-zero elements on the diagonalD is exactly the rank ofA.^[11]Some indefinite matrices for which no Cholesky decomposition exists have an LDL decomposition with negative entries inD: it suffices that the firstn − 1leading principal minors ofA are non-singular.^[12]

Here is the Cholesky decomposition of a symmetric real matrix:

And here is its LDL^T decomposition:

The Cholesky decomposition is equivalent to a particular choice ofconjugate axes of anellipsoid.^[13] In detail, let the ellipsoid be defined as$y^{T}Ay=1$, then by definition, a set of vectors$v_1,...,v_n$ are conjugate axes of the ellipsoid iff$v_i^{T}A{v}_j={\delta }_{ij}$. Then, the ellipsoid is precisely$${\displaystyle \left\{\sum _i{x}_i{v}_i:x^{T}x=1\right\}=f({\mathbb{S}}^n)}$$where$f$ maps the basis vector$e_i\mapsto v_i$, and${\mathbb{S}}^n$ is theunit sphere in n dimensions. That is, the ellipsoid is a linear image of the unit sphere.

Define the matrix$V:=[v_1|v_2|\cdots |v_n]$, then$v_i^{T}A{v}_j={\delta }_{ij}$ is equivalent to$V^{T}AV=I$. Different choices of the conjugate axes correspond to different decompositions.

The Cholesky decomposition corresponds to choosing$v_1$ to be parallel to the first axis,$v_2$ to be within the plane spanned by the first two axes, and so on. This makes$V$ an upper-triangular matrix. Then, there is$A=L{L}^T$, where$L=(V^{-1}{)}^T$ is lower-triangular.

Similarly,principal component analysis corresponds to choosing$v_1,...,v_n$ to be perpendicular. Then, let$\lambda =1/\Vert v_i{\Vert }^2$ and$\mathrm{\Sigma }=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\lambda }_1,...,{\lambda }_n)$, and there is$V=U{\mathrm{\Sigma }}^{-1/2}$ where$U$ is anorthogonal matrix. This then yields$A=U\mathrm{\Sigma }{U}^T$.

The Cholesky decomposition is mainly used for the numerical solution oflinear equations$\mathbf{A}\mathbf{x}=\mathbf{b}$. IfA is symmetric and positive definite, then$\mathbf{A}\mathbf{x}=\mathbf{b}$ can be solved by first computing the Cholesky decomposition$\mathbf{A}={\mathbf{L}\mathbf{L}}^{\ast }$, then solving$\mathbf{L}\mathbf{y}=\mathbf{b}$ fory byforward substitution, and finally solving${\mathbf{L}}^{\mathbf{\ast }}\mathbf{x}=\mathbf{y}$ forx byback substitution.

An alternative way to eliminate taking square roots in the${\mathbf{L}\mathbf{L}}^{\ast }$ decomposition is to compute the LDL decomposition$\mathbf{A}={\mathbf{L}\mathbf{D}\mathbf{L}}^{\ast }$, then solving$\mathbf{L}\mathbf{y}=\mathbf{b}$ fory, and finally solving${\mathbf{D}\mathbf{L}}^{\ast }\mathbf{x}=\mathbf{y}$.

For linear systems that can be put into symmetric form, the Cholesky decomposition (or its LDL variant) is the method of choice, for superior efficiency andnumerical stability. Compared to theLU decomposition, it is roughly twice as efficient.^[2]

Inlinear least squares problem one seeks a solutionx of an over-determined systemAx =l, such that quadratic norm of the residual vectorAx-l is minimum. This may be accomplished by solving by Cholesky decompositionnormal equations${\displaystyle \mathbf{N}\mathbf{x}={\mathbf{A}}^{\mathsf{T}}\mathbf{l}}$, where${\displaystyle \mathbf{N}={\mathbf{A}}^{\mathsf{T}}\mathbf{A}}$ is symmetric positive definite. Symmetric equation matrixmay also come from an energy functional, which must be positive from physical considerations; this happens frequently in the numerical solution ofpartial differential equations.

Such method is economic and works well in many applications, however it fails for near singularN. This is best illustrated in pathological case of square${\displaystyle \mathbf{A}}$,where determinant ofN is square of that of the original systemAx =l.Then it is best to apply SVD or QR decomposition. Givens QR has the advantage that similarlyto normal equations there is no need to keep the whole matrixA as it ispossible to update Cholesky factor with consecutive rows ofA.

Non-linear least squares are a particular case of nonlinear optimization. Let$\mathbf{f}(\mathbf{x})=\mathbf{l}$ be an over-determined system of equations with a non-linear function${\displaystyle \mathbf{f}}$ returning vector results. The aim is to minimize square norm of residuals$\mathbf{v}=\mathbf{f}(\mathbf{x})-\mathbf{l}$. An approximateNewton's method solution is obtained by expanding${\displaystyle \mathbf{f}}$ into curtailed Taylor series${\displaystyle \mathbf{f}\mathbf{(}{\mathbf{x}}_0\mathbf{+}\delta \mathbf{x}\mathbf{)}\approx \mathbf{f}\mathbf{(}{\mathbf{x}}_0\mathbf{)}\mathbf{+}\mathbf{(}\mathrm{\partial }\mathbf{f}\mathbf{/}\mathrm{\partial }\mathbf{x}\mathbf{)}\delta \mathbf{x}}$ yieldinglinear least squares problem for${\displaystyle \delta \mathbf{x}}$

${\displaystyle \mathbf{(}\mathrm{\partial }\mathbf{f}\mathbf{/}\mathrm{\partial }\mathbf{x}\mathbf{)}\delta \mathbf{x}\mathbf{=}\mathbf{l}\mathbf{-}\mathbf{f}\mathbf{(}{\mathbf{x}}_0\mathbf{)}\mathbf{=}\mathbf{v}\mathbf{,}\underset{\delta \mathbf{x}}{min}\mathbf{=}\Vert \mathbf{v}{\Vert }^{\mathbf{2}}.}$

Of course because of neglect of higher Taylor terms such solution is only approximate, if it ever exists. Now one could update expansion point to${\displaystyle {\mathbf{x}}_{\mathrm{n}+1}\mathbf{=}{\mathbf{x}}_{\mathrm{n}}\mathbf{+}\delta \mathbf{x}}$and repeat the whole procedure, hoping that (i) iterations converge to a solutionand (ii) that the solution is the one needed. Unfortunately neither is guaranteed andmust be verified.

Non-linear least squares may be also applied to the linear least squares problem by setting${\displaystyle {\mathbf{x}}_0\mathbf{=}\mathbf{0}}$ and${\displaystyle \mathbf{f}\mathbf{(}{\mathbf{x}}_0\mathbf{)}\mathbf{=}\mathbf{A}\mathbf{x}}$. This may be useful if Cholesky decomposition yields an inaccurate inverse${\displaystyle {\mathbf{R}}^{-1}}$ for the triangle matrix where${\displaystyle {\mathbf{R}}^{\mathrm{T}}\mathbf{R}\mathbf{=}\mathbf{N}}$, because of rounding errors. Such a procedure is called adifferential correction of the solution. As long as iterations converge, by virtue of theBanach fixed-point theorem they yield the solution with a precision that is only limited by the precision of the calculated residuals${\displaystyle \mathbf{v}\mathbf{=}\mathbf{A}\mathbf{x}\mathbf{-}\mathbf{l}}$. The precision is independent rounding errors in${\displaystyle {\mathbf{R}}^{-1}}$. Poor${\displaystyle {\mathbf{R}}^{-1}}$ may restrict region of initial${\displaystyle {\mathbf{x}}_0}$yielding convergence or altogether preventing it. Usually convergence is slower e.g. linearso that${\displaystyle \Vert \delta {\mathbf{x}}_{\mathrm{n}+1}\Vert \approx \Vert \mathbf{=}\alpha \delta {\mathbf{x}}_{\mathrm{n}}\Vert }$ where constant. Such slow convergence may be sped byAitken${\displaystyle {\delta }^2}$ method.If calculation of${\displaystyle {\mathbf{R}}^{-1}}$ is very costly, it is possible to use it from previous iterations as long as convergence is maintained. Such Cholesky procedure may work even for Hilbert matrices, notoriously difficult to invert.^[14]

Non-linear multi-variate functions may be minimized over their parameters using variants ofNewton's method calledquasi-Newton methods. At iteration k, the search steps in a direction$p_k$ defined by solving$B_k{p}_k=-g_k$ for$p_k$, where$p_k$ is the step direction,$g_k$ is thegradient, and$B_k$ is an approximation to theHessian matrix formed by repeating rank-1 updates at each iteration. Two well-known update formulas are calledDavidon–Fletcher–Powell (DFP) andBroyden–Fletcher–Goldfarb–Shanno (BFGS). Loss of the positive-definite condition through round-off error is avoided if rather than updating an approximation to the inverse of the Hessian, one updates the Cholesky decomposition of an approximation of the Hessian matrix itself.^[15]

The Cholesky decomposition is commonly used in theMonte Carlo method for simulating systems with multiple correlated variables. Thecovariance matrix is decomposed to give the lower-triangularL. Applying this to a vector of uncorrelated observations in a sampleu produces a sample vectorLu with the covariance properties of the system being modeled.^[16]

The following simplified example shows the economy one gets from the Cholesky decomposition: suppose the goal is to generate two correlated normal variables$x_1$ and$x_2$ with given correlation coefficient$\rho$. To accomplish that, it is necessary to first generate two uncorrelated Gaussian random variables$z_1$ and$z_2$ (for example, via aBox–Muller transform). Given the required correlation coefficient$\rho$, the correlated normal variables can be obtained via the transformations$x_1=z_1$ and$x_2=\rho z_1+\sqrt{1-{\rho }^2}{z}_2$.

Unscented Kalman filters commonly use the Cholesky decomposition to choose a set of so-called sigma points. The Kalman filter tracks the average state of a system as a vectorx of lengthN and covariance as anN ×N matrixP. The matrixP is always positive semi-definite and can be decomposed intoLL^T. The columns ofL can be added and subtracted from the meanx to form a set of2N vectors calledsigma points. These sigma points completely capture the mean and covariance of the system state.

The explicitinverse of a Hermitian matrix can be computed by Cholesky decomposition, in a manner similar to solving linear systems, using$n^3$ operations ($\frac{1}{2}{n}^3$ multiplications).^[10] The entire inversion can even be efficiently performed in-place.

A non-Hermitian matrixB can also be inverted using the following identity, whereBB* will always be Hermitian:

$${\displaystyle {\mathbf{B}}^{-1}={\mathbf{B}}^{\ast }({\mathbf{B}\mathbf{B}}^{\ast }{)}^{-1}.}$$

Cholesky decomposition can also be used to impute data. Variations of the expectation maximization algorithm among other data imputation algorithms, make use of Cholesky decomposition.^[17]

There are various methods for calculating the Cholesky decomposition. The computational complexity of commonly used algorithms isO(n³) in general.^{[citation needed]} The algorithms described below all involve about(1/3)n³FLOPs (n³/6 multiplications and the same number of additions) for real flavors and(4/3)n³FLOPs for complex flavors,^[18] wheren is the size of the matrixA. Hence, they have half the cost of theLU decomposition, which uses2n³/3 FLOPs (see Trefethen and Bau 1997).

Which of the algorithms below is faster depends on the details of the implementation. Generally, the first algorithm will be slightly slower because it accesses the data in a less regular manner.The Cholesky decomposition was shown to be numerically stable without need for pivoting.^[19]

TheCholesky algorithm, used to calculate the decomposition matrixL, is a modified version ofGaussian elimination.

The recursive algorithm starts withi := 1 and

A⁽¹⁾ :=A.

At stepi, the matrixA⁽ⁱ⁾ has the following form:whereI_i−1 denotes theidentity matrix of dimensioni − 1.

If the matrixL_i is defined by(note thata_i,i > 0 sinceA⁽ⁱ⁾ is positive definite),thenA⁽ⁱ⁾ can be written as$${\displaystyle {\mathbf{A}}^{(i)}={\mathbf{L}}_i{\mathbf{A}}^{(i+1)}{\mathbf{L}}_i^{\ast }}$$whereNote thatb_ib_i* is anouter product, therefore this algorithm is called theouter-product version in (Golub & Van Loan).

This is repeated fori from 1 ton. Aftern steps,A⁽ⁿ⁺¹⁾ =I is obtained, and hence, the lower triangular matrixL sought for is calculated as

$${\displaystyle \mathbf{L}:={\mathbf{L}}_1{\mathbf{L}}_2\dots {\mathbf{L}}_n.}$$

If the equation

is written out, the following is obtained:

and therefore the following formulas for the entries ofL:

$${\displaystyle L_{j,j}=(\pm )\sqrt{A_{j,j}-\sum _{k=1}^{j-1}{L}_{j,k}^2},}$$$${\displaystyle L_{i,j}=\frac{1}{L_{j,j}}\left(A_{i,j}-\sum _{k=1}^{j-1}{L}_{i,k}{L}_{j,k}\right)\text{for }i>j.}$$

For complex and real matrices, inconsequential arbitrary sign changes of diagonal and associated off-diagonal elements are allowed. The expression under thesquare root is always positive ifA is real and positive-definite.

For complex Hermitian matrix, the following formula applies:

$${\displaystyle L_{j,j}=\sqrt{A_{j,j}-\sum _{k=1}^{j-1}{L}_{j,k}^{\ast }{L}_{j,k}},}$$$${\displaystyle L_{i,j}=\frac{1}{L_{j,j}}\left(A_{i,j}-\sum _{k=1}^{j-1}{L}_{j,k}^{\ast }{L}_{i,k}\right)\text{for }i>j.}$$

and it can be shown that${\displaystyle L_{j,j}}$ is alwaysreal and positive ifA is positive-definite.^[20]: 49

So it now is possible to compute the(i,j) entry if the entries to the left and above are known. The computation is usually arranged in either of the following orders:

• TheCholesky–Banachiewicz algorithm starts from the upper left corner of the matrixL and proceeds to calculate the matrix row by row.

for(i=0;i<dimensionSize;i++){for(j=0;j<=i;j++){floatsum=0;for(k=0;k<j;k++)sum+=L[i][k]*L[j][k];if(i==j)L[i][j]=sqrt(A[i][i]-sum);elseL[i][j]=(1.0/L[j][j]*(A[i][j]-sum));}}

The above algorithm can be succinctly expressed as combining adot product andmatrix multiplication in vectorized programming languages such asFortran as the following,

doi=1,size(A,1)L(i,i)=sqrt(A(i,i)-dot_product(L(i,1:i-1),L(i,1:i-1)))L(i+1:,i)=(A(i+1:,i)-matmul(conjg(L(i,1:i-1)),L(i+1:,1:i-1)))/L(i,i)end do

whereconjg refers to complex conjugate of the elements.

• TheCholesky–Crout algorithm starts from the upper left corner of the matrixL and proceeds to calculate the matrix column by column.

  for(j=0;j<dimensionSize;j++){floatsum=0;for(k=0;k<j;k++){sum+=L[j][k]*L[j][k];}L[j][j]=sqrt(A[j][j]-sum);for(i=j+1;i<dimensionSize;i++){sum=0;for(k=0;k<j;k++){sum+=L[i][k]*L[j][k];}L[i][j]=(1.0/L[j][j]*(A[i][j]-sum));}}

The above algorithm can be succinctly expressed as combining adot product andmatrix multiplication in vectorized programming languages such asFortran as the following,

doi=1,size(A,1)L(i,i)=sqrt(A(i,i)-dot_product(L(1:i-1,i),L(1:i-1,i)))L(i,i+1:)=(A(i,i+1:)-matmul(conjg(L(1:i-1,i)),L(1:i-1,i+1:)))/L(i,i)end do

whereconjg refers to complex conjugate of the elements.

Either pattern of access allows the entire computation to be performed in-place if desired.

Suppose that there is a desire to solve awell-conditioned system of linear equations. If the LU decomposition is used, then the algorithm is unstable unless some sort of pivoting strategy is used. In the latter case, the error depends on the so-called growth factor of the matrix, which is usually (but not always) small.

Now, suppose that the Cholesky decomposition is applicable. As mentioned above, the algorithm will be twice as fast. Furthermore, nopivoting is necessary, and the error will always be small. Specifically, ifAx =b, andy denotes the computed solution, theny solves the perturbed system (A +E)y =b, where$${\displaystyle \Vert \mathbf{E}{\Vert }_2\le c_n\epsilon \Vert \mathbf{A}{\Vert }_2.}$$Here ||·||₂ is thematrix 2-norm,c_n is a small constant depending onn, andε denotes theunit round-off.

One concern with the Cholesky decomposition to be aware of is the use of square roots. If the matrix being factorized is positive definite as required, the numbers under the square roots are always positivein exact arithmetic. Unfortunately, the numbers can become negative because ofround-off errors, in which case the algorithm cannot continue. However, this can only happen if the matrix is very ill-conditioned. One way to address this is to add a diagonal correction matrix to the matrix being decomposed in an attempt to promote the positive-definiteness.^[21] While this might lessen the accuracy of the decomposition, it can be very favorable for other reasons; for example, when performingNewton's method in optimization, adding a diagonal matrix can improve stability when far from the optimum.

An alternative form, eliminating the need to take square roots whenA is symmetric, is the symmetric indefinite factorization^[20]: 84

The following recursive relations apply for the entries ofD andL:$${\displaystyle D_j=A_{jj}-\sum _{k=1}^{j-1}{L}_{jk}^2{D}_k,}$$$${\displaystyle L_{ij}=\frac{1}{D_j}\left(A_{ij}-\sum _{k=1}^{j-1}{L}_{ik}{L}_{jk}{D}_k\right)\text{for }i>j.}$$

This works as long as the generated diagonal elements inD stay non-zero. The decomposition is then unique.D andL are real ifA is real.

For complex Hermitian matrixA, the following formula applies:

$${\displaystyle D_j=A_{jj}-\sum _{k=1}^{j-1}{L}_{jk}{L}_{jk}^{\ast }{D}_k,}$$$${\displaystyle L_{ij}=\frac{1}{D_j}\left(A_{ij}-\sum _{k=1}^{j-1}{L}_{ik}{L}_{jk}^{\ast }{D}_k\right)\text{for }i>j.}$$

Again, the pattern of access allows the entire computation to be performed in-place if desired.

When used on indefinite matrices, theLDL* factorization is known to be unstable without careful pivoting;^[22] specifically, the elements of the factorization can grow arbitrarily. A possible improvement is to perform the factorization on block sub-matrices, commonly 2 × 2:^[23]

where every element in the matrices above is a square submatrix. From this, these analogous recursive relations follow:

$${\displaystyle {\mathbf{D}}_j={\mathbf{A}}_{jj}-\sum _{k=1}^{j-1}{\mathbf{L}}_{jk}{\mathbf{D}}_k{\mathbf{L}}_{jk}^{\mathrm{T}},}$$$${\displaystyle {\mathbf{L}}_{ij}=\left({\mathbf{A}}_{ij}-\sum _{k=1}^{j-1}{\mathbf{L}}_{ik}{\mathbf{D}}_k{\mathbf{L}}_{jk}^{\mathrm{T}}\right){\mathbf{D}}_j^{-1}.}$$

This involves matrix products and explicit inversion, thus limiting the practical block size.

A task that often arises in practice is that one needs to update a Cholesky decomposition. In more details, one has already computed the Cholesky decomposition$\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\ast }$ of some matrix$\mathbf{A}$, then one changes the matrix$\mathbf{A}$ in some way into another matrix, say$\tilde{\mathbf{A}}$, and one wants to compute the Cholesky decomposition of the updated matrix:$\tilde{\mathbf{A}}=\tilde{\mathbf{L}}{\tilde{\mathbf{L}}}^{\ast }$. The question is now whether one can use the Cholesky decomposition of$\mathbf{A}$ that was computed before to compute the Cholesky decomposition of$\tilde{\mathbf{A}}$.

The specific case, where the updated matrix$\tilde{\mathbf{A}}$ is related to the matrix$\mathbf{A}$ by$\tilde{\mathbf{A}}=\mathbf{A}+c\mathbf{x}{\mathbf{x}}^{\ast }$, is known as arank-one update. Here the constant${\displaystyle c}$ is allowed to be negative, but must always be such that the new matrix$\tilde{\mathbf{A}}$ is still positive definite.

Here is a function^[24] written inMatlab syntax that realizes a rank-one update:

functionL=updateChol(L,x,c)% given the L*L' Cholesky decomposition of a matrix, compute the updated% factor L so that we have the Cholesky decomposition of L*L'+c*x*x';n=length(x);fork=1:n-1l=L(:,k);% old value of k-th columnlk=l(k);xk=x(k);dk=sqrt(lk^2+c*xk^2);% new diagonal valueL(:,k)=(lk/dk)*l+(c*xk/dk)*x;% new column valuex=x-l*(xk/lk);c=c*(lk/dk)^2;endL(n,n)=sqrt(L(n,n)^2+c*x(n)^2);end

Arank-n update is one where for a matrix$\mathbf{M}$ one updates the decomposition such that$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{M}{\mathbf{M}}^{\ast }$. This can be achieved by successively performing rank-one updates for each of the columns of$\mathbf{M}$.

If a symmetric and positive definite matrix$\mathbf{A}$ is represented in block form as

and its upper Cholesky factor

then for a new matrix$\tilde{\mathbf{A}}$, which is the same as$\mathbf{A}$ but with the insertion of new rows and columns,

Now there is an interest in finding the Cholesky factorization of$\tilde{\mathbf{A}}$, which can be called$\tilde{\mathbf{S}}$, without directly computing the entire decomposition.

Writing$\mathbf{A}\setminus \mathbf{b}$ for the solution of$\mathbf{A}\mathbf{x}=\mathbf{b}$, which can be found easily for triangular matrices, and$\text{chol}(\mathbf{M})$ for the Cholesky decomposition of$\mathbf{M}$, the following relations can be found:

These formulas may be used to determine the Cholesky factor after the insertion of rows or columns in any position, if the row and column dimensions are appropriately set (including to zero). The inverse problem,

with known Cholesky decomposition

and the desire to determine the Cholesky factor

of the matrix$\mathbf{A}$ with rows and columns removed,

yields the following rules:

Notice that the equations above that involve finding the Cholesky decomposition of a new matrix are all of the form$\tilde{\mathbf{A}}=\mathbf{A}+c\mathbf{x}{\mathbf{x}}^{\ast }$ for some constant${\displaystyle c=\pm 1}$, which allows them to be efficiently calculated using procedure detailed in the previous section.^[24]

The above algorithms show that every positive definite matrix$\mathbf{A}$ has a Cholesky decomposition. This result can be extended to the positive semi-definite case by a limiting argument. The argument is not fully constructive, i.e., it gives no explicit numerical algorithms for computing Cholesky factors.

If$\mathbf{A}$ is an$n\times n$positive semi-definite matrix, then the sequence${\left({\mathbf{A}}_k\right)}_k:={\left(\mathbf{A}+\frac{1}{k}{\mathbf{I}}_n\right)}_k$ consists ofpositive definite matrices. (This is an immediate consequence of, for example, the spectral mapping theorem for the polynomial functional calculus.) Also,$${\displaystyle {\mathbf{A}}_k\to \mathbf{A}\text{for}k\to \mathrm{\infty }}$$ inoperator norm. From the positive definite case, each${\mathbf{A}}_k$ has Cholesky decomposition${\mathbf{A}}_k={\mathbf{L}}_k{\mathbf{L}}_k^{\ast }$. By property of the operator norm,

$${\displaystyle \Vert {\mathbf{L}}_k{\Vert }^2\le \Vert {\mathbf{L}}_k{\mathbf{L}}_k^{\ast }\Vert =\Vert {\mathbf{A}}_k\Vert .}$$

The$\le$ holds because$M_n(\mathbb{C})$ equipped with the operator norm is a C* algebra. So${\left({\mathbf{L}}_k\right)}_k$ is a bounded set in theBanach space of operators, thereforerelatively compact (because the underlyingvector space is finite-dimensional). Consequently, it has a convergent subsequence, also denoted by${\left({\mathbf{L}}_k\right)}_k$, with limit$\mathbf{L}$. It can be easily checked that this$\mathbf{L}$ has the desired properties, i.e.$\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\ast }$, and$\mathbf{L}$ is lower triangular with non-negative diagonal entries: for all$x$ and$y$,

$${\displaystyle ⟨\mathbf{A}x,y⟩=⟨lim{\mathbf{A}}_{k}x,y⟩=⟨lim{\mathbf{L}}_k{\mathbf{L}}_k^{\ast }x,y⟩=⟨\mathbf{L}{\mathbf{L}}^{\ast }x,y⟩.}$$

Therefore,$\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\ast }$. Because the underlying vector space is finite-dimensional, all topologies on the space of operators are equivalent. So${\left({\mathbf{L}}_k\right)}_k$ tends to$\mathbf{L}$ in norm means${\left({\mathbf{L}}_k\right)}_k$ tends to$\mathbf{L}$ entrywise. This in turn implies that, since each${\mathbf{L}}_k$ is lower triangular with non-negative diagonal entries,$\mathbf{L}$ is also.

Let$\mathbf{A}$ be apositive semi-definite Hermitian matrix. Then it can be written as a product of itssquare root matrix,$\mathbf{A}=\mathbf{B}{\mathbf{B}}^{\ast }$. NowQR decomposition can be applied to${\mathbf{B}}^{\ast }$, resulting in${\mathbf{B}}^{\ast }=\mathbf{Q}\mathbf{R}$, where$\mathbf{Q}$ is unitary and$\mathbf{R}$ is upper triangular. Inserting the decomposition into the original equality yields$A=\mathbf{B}{\mathbf{B}}^{\ast }=(\mathbf{Q}\mathbf{R}{)}^{\ast }\mathbf{Q}\mathbf{R}={\mathbf{R}}^{\ast }{\mathbf{Q}}^{\ast }\mathbf{Q}\mathbf{R}={\mathbf{R}}^{\ast }\mathbf{R}$. Setting$\mathbf{L}={\mathbf{R}}^{\ast }$ completes the proof.

The Cholesky factorization can be generalized^{[citation needed]} to (not necessarily finite) matrices with operator entries. Let$\{{\mathcal{H}}_n\}$ be a sequence ofHilbert spaces. Consider the operator matrix

acting on the direct sum

$${\displaystyle \mathcal{H}=\underset{n}{⨁}{\mathcal{H}}_n,}$$

where each

$${\displaystyle {\mathbf{A}}_{ij}:{\mathcal{H}}_j\to {\mathcal{H}}_i}$$

is abounded operator. IfA is positive (semidefinite) in the sense that for all finitek and for any

$${\displaystyle h\in \underset{n=1}{\overset{k}{⨁}}{\mathcal{H}}_k,}$$

there is$⟨h,\mathbf{A}h⟩\ge 0$, then there exists a lower triangular operator matrixL such thatA =LL*. One can also take the diagonal entries ofL to be positive.

• C programming language: theGNU Scientific Library provides several implementations of Cholesky decomposition.
• Maximacomputer algebra system: functioncholesky computes Cholesky decomposition.
• GNU Octave numerical computations system provides several functions to calculate, update, and apply a Cholesky decomposition.
• TheLAPACK library provides a high performance implementation of the Cholesky decomposition that can be accessed fromFortran,C and most languages. The Cholesky decomposition is available through the*POTRF family of subroutines, and the LDL decomposition through the*HETRF family of subroutines.
• InPython, the functioncholesky from thenumpy.linalg module performs Cholesky decomposition. Thescipy.linalg module contains theldl function for the LDL decomposition.
• InMatlab, thechol function gives the Cholesky decomposition. Note thatchol uses the upper triangular factor of the input matrix by default, i.e. it computes$A=R^{\ast }R$ where$R$ is upper triangular. A flag can be passed to use the lower triangular factor instead.
• InR, thechol function gives the Cholesky decomposition.
• InJulia, thecholesky function from theLinearAlgebra standard library gives the Cholesky decomposition.
• InMathematica, the function "CholeskyDecomposition" can be applied to a matrix.
• InC++, multiple linear algebra libraries support this decomposition:
  • TheArmadillo (C++ library) supplies the commandchol to perform Cholesky decomposition.
  • TheEigen library supplies Cholesky factorizations for both sparse and dense matrices.
  • In theROOT package, theTDecompChol class is available.

• InAnalytica, the functionDecompose gives the Cholesky decomposition.
• TheApache Commons Math library has an implementation which can be used in Java, Scala and any other JVM language.

• Cycle rank
• Incomplete Cholesky factorization
• Matrix decomposition
• Minimum degree algorithm
• Square root of a matrix
• Sylvester's law of inertia
• Symbolic Cholesky decomposition

• Dereniowski, Dariusz; Kubale, Marek (2004). "Cholesky Factorization of Matrices in Parallel and Ranking of Graphs".5th International Conference on Parallel Processing and Applied Mathematics(PDF). Lecture Notes on Computer Science. Vol. 3019. Springer-Verlag. pp. 985–992.doi:10.1007/978-3-540-24669-5_127.ISBN 978-3-540-21946-0. Archived fromthe original(PDF) on 2011-07-16.
• Golub, Gene H.;Van Loan, Charles F. (1996).Matrix Computations (3rd ed.). Baltimore: Johns Hopkins.ISBN 978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985).Matrix Analysis. Cambridge University Press.ISBN 0-521-38632-2.
• S. J. Julier and J. K. Uhlmann. "A General Method for Approximating Nonlinear Transformations of ProbabilityDistributions".
• S. J. Julier and J. K. Uhlmann, "A new extension of the Kalman filter to nonlinear systems", in Proc. AeroSense: 11th Int. Symp. Aerospace/Defence Sensing, Simulation and Controls, 1997, pp. 182–193.
• Trefethen, Lloyd N.; Bau, David (1997).Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics.ISBN 978-0-89871-361-9.
• Osborne, Michael (2010).Bayesian Gaussian Processes for Sequential Prediction, Optimisation and Quadrature(PDF) (thesis). University of Oxford.
• Ruschel, João Paulo Tarasconi, Bachelor degree "Parallel Implementations of the Cholesky Decomposition on CPUs and GPUs" Universidade Federal Do Rio Grande Do Sul, Instituto De Informatica, 2016, pp. 29-30.

• Sur la résolution numérique des systèmes d'équations linéaires, Cholesky's 1910 manuscript, online and analyzed onBibNum(in French and English)[for English, click 'A télécharger']

• "Cholesky factorization".Encyclopedia of Mathematics.EMS Press. 2001 [1994].
• Cholesky Decomposition, The Data Analysis BriefBook
• Cholesky Decomposition on www.math-linux.com
• Cholesky Decomposition Made Simple on Science Meanderthal

• LAPACK is a collection of FORTRAN subroutines for solving dense linear algebra problems (DPOTRF, DPOTRF2,detailsperformance)
• ALGLIB includes a partial port of the LAPACK to C++, C#, Delphi, Visual Basic, etc. (spdmatrixcholesky, hpdmatrixcholesky)
• libflame is a C library with LAPACK functionality.
• Notes and video on high-performance implementation of Cholesky factorization at The University of Texas at Austin.
• Cholesky : TBB + Threads + SSE is a book explaining the implementation of the CF with TBB, threads and SSE (in Spanish).
• library "Ceres Solver" by Google.
• LDL decomposition routines in Matlab.
• Armadillo is a C++ linear algebra package
• Rosetta Code is a programming chrestomathy site.on page topic.
• AlgoWiki is an open encyclopedia of algorithms’ properties and features of their implementationson page topic
• Intel® oneAPI Math Kernel Library Intel-Optimized Math Library for Numerical Computing?potrf,?potrs

• Generating Correlated Random Variables and Stochastic Processes, Martin Haugh,Columbia University

• Online Matrix Calculator Performs Cholesky decomposition of matrices online.

• Operator theory
• Matrix decompositions
• Numerical linear algebra

• CS1 French-language sources (fr)
• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from June 2011
• Articles with unsourced statements from October 2016
• Articles with French-language sources (fr)
• Articles with example MATLAB/Octave code