Rectangular Matrix LU Decomposition (LU Decomposition)

From Algorithm Wiki
Jump to navigation Jump to search


Lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. In the general case, the input is an $m \times n$ matrix.

Related Problems

Subproblem: Square Matrix LU Decomposition


$m$: number of rows in input matrix

$n$: number of columns in input matrix

$l$: number of columns chosen to use in the decomposition ($l \geq k$)

$k$: desired rank of decomposition

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Randomized LU Decomposition 2016 $O(n^{3})$ $\tilde{O}(nl + ml)$ See Theorem 4.3 in original paper for error bound Randomized Time