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 |
||
| 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 == | ||
Revision as of 13:02, 15 February 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 |
|---|---|---|---|---|---|---|
| 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 |