Randomized Algorithms For LU Decomposition And Cholesky Decomposition

LU decomposition algorithms of matrix is an important research branch in numerical linear algebra,and it is widely used in scientific and engineering calculation.In the era of big data,traditional deterministic algorithms are difficult to meet the requirements of practical applications because of the high cost of calculation and data transfer.The problem can be solved efficiently more with the randomized versions by scholars.However,the algorithms need two passes over the original matrix at least,they are not suitable for extremely large and high-dimensional matrix stored outside of core memory or generated in a streaming fashion.Therefore,based on the random algorithms of LU decomposition,we present the single-pass randomized algorithms,which only need to pass the original matrix once.Moreover,a new randomized algorithm for Cholesky decomposition is also considered.The specific contents are as follows:For LU decomposition,we mainly present three single-pass randomized algorithms,i.e.regular single-pass randomized algorithm,subspace-Orbit single-pass randomized algorithm and two-sided single-pass randomized algorithm.The rigorous error bounds and complexities of these algorithms are provided.Meanwhile,the pros and cons of each algorithm and its limitations for different streaming data are compared.Numerical experiments show that these single-pass algorithms have the similar accuracy and run time compared with the state-of-the-art randomized algorithms for LU decomposition,without considering the cost of reading the original data.It is mentioned that the singlepass randomized algorithms have a significant advantage in total complexity cost because the cost of matrix transfer is generally higher than the cost of the algorithm for big scale data.For Cholesky decomposition,we present a new randomized algorithm,then the rigorous error bound and complexity are provided.Numerical experiments show that the new randomized version of Cholesky decomposition has a better performance in lowrank approximations compared with the state-of-the-art randomized algorithm and the diagonal pivoted Cholesky decomposition.