Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Cholesky decomposition
Summary
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ʃəˈlɛski ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for efficient numerical solutions, e.g., Monte Carlo simulations. It was discovered by André-Louis Cholesky for real matrices, and posthumously published in 1924.
When it is applicable, the Cholesky decomposition is roughly twice as efficient as the LU decomposition for solving systems of linear equations.
The Cholesky decomposition of a Hermitian positive-definite matrix A, is a decomposition of the form
where L is a lower triangular matrix with real and positive diagonal entries, and L* denotes the conjugate transpose of L. Every Hermitian positive-definite matrix (and thus also every real-valued symmetric positive-definite matrix) has a unique Cholesky decomposition.
The converse holds trivially: if A can be written as LL* for some invertible L, lower triangular or otherwise, then A is Hermitian and positive definite.
When A is a real matrix (hence symmetric positive-definite), the factorization may be written
where L is a real lower triangular matrix with positive diagonal entries.
If a Hermitian matrix A is only positive semidefinite, instead of positive definite, then it still has a decomposition of the form A = LL* where the diagonal entries of L are allowed to be zero.
The decomposition need not be unique, for example:
However, if the rank of A is r, then there is a unique lower triangular L with exactly r positive diagonal elements and n−r columns containing all zeroes.
Alternatively, the decomposition can be made unique when a pivoting choice is fixed. Formally, if A is an n × n positive semidefinite matrix of rank r, then there is at least one permutation matrix P such that P A PT has a unique decomposition of the form P A PT = L L* with
where L1 is an r × r lower triangular matrix with positive diagonal.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (32)
MATH-111(e): Linear Algebra
L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications.
MATH-251(b): Numerical analysis
The students will learn key numerical techniques for solving standard mathematical problems in science and engineering. The underlying mathematical theory and properties are discussed.
PHYS-332: Computational physics III
This course teaches the students practical skills needed for solving modern physics problems by means of computation. A number of examples illustrate the utility of numerical computations in various d
Related lectures (247)
Optimal Gain of Linear Systems
Explains optimal gain in linear systems and explores Cholesky decomposition, Orr mechanism, and lift-up mechanism in fluid dynamics.
Linear Systems: Convergence and Methods
Explores linear systems, convergence, and solving methods with a focus on CPU time and memory requirements.
Harmonic Forms and Riemann Surfaces
Explores harmonic forms on Riemann surfaces, covering uniqueness of solutions and the Riemann bilinear identity.
Related publications (279)
Related people (42)
Related units (2)
Related concepts (18)
Eigendecomposition of a matrix
In linear algebra, eigendecomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way. When the matrix being factorized is a normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the spectral theorem. Eigenvalue, eigenvector and eigenspace A (nonzero) vector v of dimension N is an eigenvector of a square N × N matrix A if it satisfies a linear equation of the form for some scalar λ.
Invertible matrix
In linear algebra, an n-by-n square matrix A is called invertible (also nonsingular, nondegenerate or (rarely used) regular), if there exists an n-by-n square matrix B such that where In denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. If this is the case, then the matrix B is uniquely determined by A, and is called the (multiplicative) inverse of A, denoted by A−1. Matrix inversion is the process of finding the matrix B that satisfies the prior equation for a given invertible matrix A.
LU decomposition
In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix decomposition). The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix.
Related MOOCs (9)
Algebra (part 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algebra (part 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algebra (part 2)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.