Randomized LU Decomposition

We present a fast randomized algorithm that computes a low rank LU decomposition. The algorithm uses random projections type techniques to efficiently compute a low rank approximation of large matrices. The randomized LU algorithm can be parallelized and further accelerated by using sparse random matrices in its projection step. Several error bounds for the algorithm’s approximations are proved. To prove these bounds, recent results from random matrix theory related to subgaussian matrices are used. The algorithm, which can utilize sparse structures, is fully parallelized and thus can utilize efficiently GPUs. Numerical examples, which illustrate the performance of the algorithm and compare it to other decomposition methods, are presented