Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition)

Time Complexity

$O(n^{3})$

$\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$)

Approximate

Approximation Factor: See Theorem 4.3 in original paper for error bound

Yes, Monte Carlo

Word RAM

2016