Solving Systems of Linear Algebraic Equations Using a Randomized SVD Algorithm

In the paper, we implement and compare two randomized algorithms for constructing truncated singular value decompositions (SVD) for large matrices. The first one, a sampling algorithm, is based on a random sampling of a subset of matrix rows and columns to which the standard SVD algorithm is applied. This subset’s singular values and vectors are then used to recover the SVD of the original large matrix. The projection method uses a random Gaussian matrix to find random subspaces of lower dimensions with their orthonormal basis. A low-rank approximation of the original matrix is computed using this orthonormal basis, which subsequently results in the approximation of the truncated SVD. Since the dimension of the subspace is much smaller than the rank of the original matrix, randomized methods speed up the computation of near-optimal decompositions of the large matrix. In this paper, both projection and sampling algorithms are used to apply randomized truncated SVD to the solution of large systems of linear algebraic equations. The accuracy of the algorithms is compared depending on the size of the subspace that captures the dominant actions of the original matrix on two test matrices: a general matrix and a low-rank matrix. We implement parallel versions of the algorithms using the OpenMP interface and compare their performance.