Rectangular Matrix LU Decomposition: Difference between revisions
Jump to navigation
Jump to search
(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...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
$m$: number of rows in input matrix | |||
$n$: number of columns in input matrix | $n$: number of columns in input matrix | ||
$l$: number of columns chosen to use in the decomposition ($l \geq k$) | $l$: number of columns chosen to use in the decomposition ($l \geq k$) | ||
$k$: desired rank of decomposition | |||
$k$: desired rank of decomposition | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 23: | 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 |