Skip to main content
Select Source:

Cholesky Decomposition

Cholesky Decomposition

BIBLIOGRAPHY

The Cholesky decomposition factorizes a positive definite matrix A into a lower triangular matrix L and its transpose, L :

A = LL

This decomposition is named after André-Louis Cholesky (1875-1918), a French artillery officer who invented the method in the context of his work in the Geodesic Section of the Army Geographic Service.

The k × k real symmetric matrix A is positive definite if and only if xAx > 0 for any nonzero k -vector. For such matrices, the corresponding Cholesky factor L (sometimes called the matrix square root ) always exists and is unique. Matrices of this sort arise in many econometric contexts, making the Cholesky decomposition a very useful computational tool. For example, it can be used to solve the normal equations of least squares to produce coefficient estimates in multiple regression analysis. In this case, the place of A is occupied by the matrix of squares and cross-products of the regressors, XX.

Given the Cholesky decomposition of A, the set of linear equations Ax = b in the unknown vector x may be written as LLx = b. Writing y for Lx, we get Ly = b, which may be solved for y, then y = Lx is solved for x. It is trivial to solve equations on the pattern Mx = b for triangular M.

Algorithms for computing the decomposition are based on the following relationships between the elements aij of A and the elements lij of L :

Element lij can be computed if we know the elements to the left and above. The Cholesky-Crout algorithm starts from the upper left corner of L and calculates the matrix column by column.

The beauty of the Cholesky method is that it is numerically stable and accurate (as noted by Turing 1948) while requiring fewer floating-point operations and less workspace (computer memory) than alternative methods. It does, however, have a problem if the matrix A is very ill-conditioned. (In the econometric context mentioned above, this occurs if there is a high degree of collinearity among the variables in the data matrix X.) Computing the decomposition requires that we calculate a sequence of square roots. The values under the square root sign in equation (2) are always positive in exact arithmetic, but for ill-conditioned A they may be very small. Given the rounding error inherent in finite-precision computer arithmetic, these values may go negativein which case the algorithm cannot continueor they may simply fall below the magnitude at which rounding error is an acceptable proportion of the computed value. A practical implementation of the Cholesky algorithm for a digital computer must check for this condition and terminate if need be. If the Cholesky method fails, one can resort to the computationally more expensive QR or SVD decomposition methods.

Besides solving sets of linear equations, the Cholesky decomposition has a further use in econometrics that deserves mention, namely, decomposing the covariance matrix for a set of residuals in the context of a vector autoregression. This sort of analysis was pioneered by Christopher Sims (1980) and quickly became popular. The role of the decomposition is to permit the simulation of the response of a system to a disturbance in any one of the variables, and also to perform an accounting of the proportions of the forecast error variance attributable to disturbances in each of the variables.

SEE ALSO Matrix Algebra

BIBLIOGRAPHY

Golub, Gene H., and Charles F. Van Loan. 1996. Matrix Computations. 3rd ed. Baltimore, MD: Johns Hopkins University Press.

OConnor, John J., and Edmund F. Robertson. 2005. André-Louis Cholesky. School of Mathematics and Statistics, University of St. Andrews: MacTutor History of Mathematics archive. http://www-history.mcs.st-andrews.ac.uk/Biographies/Cholesky.html.

Sims, Christopher. 1980. Macroeconomics and Reality. Econometrica 48 (1): 1-48.

Turing, Alan M. 1948. Rounding-Off Errors in Matrix Processes. Quarterly Journal of Mechanics and Applied Mathematics 1 (1): 287-308.

Allin Cottrell

Cite this article
Pick a style below, and copy the text for your bibliography.

  • MLA
  • Chicago
  • APA

"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Encyclopedia.com. 24 Sep. 2018 <http://www.encyclopedia.com>.

"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Encyclopedia.com. (September 24, 2018). http://www.encyclopedia.com/social-sciences/applied-and-social-sciences-magazines/cholesky-decomposition

"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Retrieved September 24, 2018 from Encyclopedia.com: http://www.encyclopedia.com/social-sciences/applied-and-social-sciences-magazines/cholesky-decomposition

Learn more about citation styles

Citation styles

Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).

Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.

Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the most-recent information available at these sites:

Modern Language Association

http://www.mla.org/style

The Chicago Manual of Style

http://www.chicagomanualofstyle.org/tools_citationguide.html

American Psychological Association

http://apastyle.apa.org/

Notes:
  • Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
  • In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.

Cholesky decomposition

Cholesky decomposition See LU decomposition.

Cite this article
Pick a style below, and copy the text for your bibliography.

  • MLA
  • Chicago
  • APA

"Cholesky decomposition." A Dictionary of Computing. . Encyclopedia.com. 24 Sep. 2018 <http://www.encyclopedia.com>.

"Cholesky decomposition." A Dictionary of Computing. . Encyclopedia.com. (September 24, 2018). http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/cholesky-decomposition

"Cholesky decomposition." A Dictionary of Computing. . Retrieved September 24, 2018 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/cholesky-decomposition

Learn more about citation styles

Citation styles

Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).

Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.

Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the most-recent information available at these sites:

Modern Language Association

http://www.mla.org/style

The Chicago Manual of Style

http://www.chicagomanualofstyle.org/tools_citationguide.html

American Psychological Association

http://apastyle.apa.org/

Notes:
  • Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
  • In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.