Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition)
Revision as of 11:38, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}(nl + ml)$ words (Derived: Two intermediate auxiliary matrices of sizes $n \times l$ and $m \times l$ for the input matrix of size $m \times n$) == Description == == Approximate? == Approximate Approximation Factor: See Theorem 4.3 in original paper for error bound == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2016 == Reference == https://www.sc...")
Time Complexity
$O(n^{3})$
Space Complexity
$\tilde{O}(nl + ml)$ words
(Derived: Two intermediate auxiliary matrices of sizes $n \times l$ and $m \times l$ for the input matrix of size $m \times n$)
Description
Approximate?
Approximate
Approximation Factor: See Theorem 4.3 in original paper for error bound
Randomized?
Yes, Monte Carlo
Model of Computation
Word RAM
Year
2016
Reference
https://www.sciencedirect.com/science/article/pii/S1063520316300069