Rectangular Matrix LU Decomposition: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 26: | Line 26: | ||
|- | |- | ||
| [[Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition)|Randomized LU Decomposition]] || 2016 || $O(n^{3})$ || $\tilde{O}(nl + ml)$ || See Theorem 4.3 in original paper for error bound || Randomized || [https://www.sciencedirect.com/science/article/pii/S1063520316300069 Time] | | [[Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition)|Randomized LU Decomposition]] || 2016 || $O(n^{3})$ || $\tilde{O}(nl + ml)$ || See Theorem 4.3 in original paper for error bound || Randomized || [https://www.sciencedirect.com/science/article/pii/S1063520316300069 Time] | ||
|- | |- | ||
|} | |} | ||
Latest revision as of 07:52, 10 April 2023
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 |
|---|---|---|---|---|---|---|
| Randomized LU Decomposition | 2016 | $O(n^{3})$ | $\tilde{O}(nl + ml)$ | See Theorem 4.3 in original paper for error bound | Randomized | Time |