**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 GraphSearch.

Concept# LU decomposition

Summary

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. The LU decomposition was introduced by the Polish astronomer Tadeusz Banachiewicz in 1938. To quote: "It appears that Gauss and Doolittle applied the method
[of elimination] only to symmetric equations. More recent authors, for example, Aitken, Banachiewicz, Dwyer, and Crout ... have emphasized the use of the method, or variations of it, in connection with non-symmetric problems ... Banachiewicz ... saw the point ... that the basic problem is really one of matrix factorization, or “decomposition” as he called it."
It's also referred to as LR decomposition (factors into left and right triangular matrices).
Let A be a square matrix. An LU factorization refers to the factorization of A, with proper row and/or column orderings or permutations, into two factors – a lower triangular matrix L and an upper triangular matrix U:
In the lower triangular matrix all elements above the diagonal are zero, in the upper triangular matrix, all the elements below the diagonal are zero. For example, for a 3 × 3 matrix A, its LU decomposition looks like this:
Without a proper ordering or permutations in the matrix, the factorization may fail to materialize. For example, it is easy to verify (by expanding the matrix multiplication) that . If , then at least one of and has to be zero, which implies that either L or U is singular. This is impossible if A is nonsingular (invertible). This is a procedural problem. It can be removed by simply reordering the rows of A so that the first element of the permuted matrix is nonzero.

Official source

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.

Related concepts (22)

Related courses (31)

Related publications (260)

Related MOOCs (11)

Related people (39)

Related lectures (320)

Related units (6)

Matrix (mathematics)

In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object. For example, is a matrix with two rows and three columns. This is often referred to as a "two by three matrix", a " matrix", or a matrix of dimension . Without further specifications, matrices represent linear maps, and allow explicit computations in linear algebra.

QR decomposition

In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix A into a product A = QR of an orthonormal matrix Q and an upper triangular matrix R. QR decomposition is often used to solve the linear least squares problem and is the basis for a particular eigenvalue algorithm, the QR algorithm. Any real square matrix A may be decomposed as where Q is an orthogonal matrix (its columns are orthogonal unit vectors meaning ) and R is an upper triangular matrix (also called right triangular matrix).

Schur complement

In linear algebra and the theory of matrices, the Schur complement of a block matrix is defined as follows. Suppose p, q are nonnegative integers, and suppose A, B, C, D are respectively p × p, p × q, q × p, and q × q matrices of complex numbers. Let so that M is a (p + q) × (p + q) matrix. If D is invertible, then the Schur complement of the block D of the matrix M is the p × p matrix defined by If A is invertible, the Schur complement of the block A of the matrix M is the q × q matrix defined by In the case that A or D is singular, substituting a generalized inverse for the inverses on M/A and M/D yields the generalized Schur complement.

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.

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

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.

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.

Dynamics: Tangential and Normal Accelerations

Explains tangential and normal accelerations, acceleration components, velocity relationships, and vehicle-ground contact conditions.

Matrix Determinant: Factorization and Linear EquationsMATH-111(e): Linear Algebra

Covers the determinant of a matrix, factorization, and linear equations with infinite solutions.

Harmonic Forms and Riemann SurfacesMATH-680: Monstrous moonshine

Explores harmonic forms on Riemann surfaces, covering uniqueness of solutions and the Riemann bilinear identity.

Cécile Hébert, Duncan Alexander, Nathanaël Perraudin, Hui Chen

We present two open-source Python packages: "electron spectro-microscopy"(espm) and "electron microscopy tables"(emtables). The espm software enables the simulation of scanning transmission electron microscopy energy-dispersive X-ray spectroscopy datacubes ...

The set of finite binary matrices of a given size is known to carry a finite type AA bicrystal structure. We first review this classical construction, explain how it yields a short proof of the equality between Kostka polynomials and one-dimensional sums t ...

2023We present an implementation of the Frenkel exciton model into the OpenMolcas program package enabling calculations of collective electronic excited states of molecular aggregates based on a multiconfigurational wave function description of the individual ...