LU decomposition
Problem Description
LU decomposition of a matrix is the factorization of a given square matrix into two triangular matrices, one upper triangular matrix and one lower triangular matrix, such that the product of these two matrices gives the original matrix. It was introduced by Alan Turing in 1948, who also created the Turing machine.
This method of factorizing a matrix as a product of two triangular matrices has various applications such as a solution of a system of equations, which itself is an integral part of many applications such as finding current in a circuit and solution of discrete dynamical system problems; finding the inverse of a matrix and finding the determinant of the matrix. Basically, the LU decomposition method comes in handy whenever it is possible to model the problem to be solved into matrix form. Conversion to the matrix form and solving with triangular matrices makes it easy to do calculations in the process of finding the solution.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | [ Doolittle algorithm (1940)]
[ Crout and LUP algorithms (1991)] [ Randomized algorithm (2016)] |
|
| Quadratic | ||
| nlogn | [ Closed formula (1975)]
[ David 2006 (2006)] [ Teukolsky; Flannery 2007 (2007)] |
|
| Linear | ||
| logn |