Rectangular Matrix LU Decomposition (LU Decomposition)
Jump to navigation
Jump to search
Description
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
Parameters
$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 |
|---|---|---|---|---|---|---|
| Closed formula | 1975 | $O(nlogn)$ | Exact | Deterministic | ||
| Randomized LU Decomposition | 2016 | $O(n^{3})$ | $\tilde{O}(nl + ml)$ | See Theorem 4.3 in original paper for error bound | Randomized | Time |
| David | 2006 | $O(nlogn)$ | Exact | Deterministic |