Rectangular Matrix LU Decomposition (LU Decomposition)
Revision as of 10:20, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rectangular Matrix LU Decomposition (LU Decomposition)}} == 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 == <pre>$m$: number of rows in input matrix $n$: number of columns in input matrix $l$: numb...")
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 |