View source for Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition)

== 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.ezproxy.canberra.edu.au/science/article/pii/S1063520316300069