Randomized LU decomposition using sparse projections. (November 2016)

• Record Type: Journal Article
• Authors: Aizenbud, Yariv; Shabat, Gil; Averbuch, Amir
• Is Part Of: Computers & mathematics with applications. Volume 72:issue 9(2016)
• Page Start: 2525
• Page End: 2534
• Publication Date: 2016-11
• Subjects: LU decomposition -- Random matrices -- Sparse matrices -- Sparse Johnson–Lindenstrauss transform; Electronic data processing -- Periodicals; Mathematics -- Data processing -- Periodicals; 510.28541
• DOI: 10.1016/j.camwa.2016.09.014
• Languages: English
• ISSNs: 0898-1221

Abstract

Abstract: A fast algorithm that approximates 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 and can fully run on a GPU. The performance is tested on a GPU card showing a significant speed-up improvement in the running time in comparison to a sequential execution.