  A fast algorithm for the approximation of a low rank LU decomposition is
presented. In order to achieve a low complexity, the algorithm uses sparse
random projections combined with FFT-based random projections. The asymptotic
approximation error of the algorithm is analyzed and a theoretical error bound
is presented. Finally, numerical examples illustrate that for a similar
approximation error, the sparse LU algorithm is faster than recent
state-of-the-art methods. The algorithm is completely parallelizable that
enables to run on a GPU. The performance is tested on a GPU card, showing a
significant improvement in the running time in comparison to sequential
execution.
