Parallel implementations of randomized vector algorithm for solving large systems of linear equations

The results of a parallel implementation of a randomized vector algorithm for solving systems of linear equations are presented in the paper. The solution is represented as a Neumann series. The stochastic method computes this series by sampling only random columns, avoiding matrix-by-matrix and matrix-by-vector multiplications. We consider the case when the matrix is too large to fit in random-access memory (RAM). We take two approaches to solving this problem. In the first approach, the matrix is divided into parts, which are distributed among the MPI processes and stored in the available RAM of the cluster nodes. In the second approach, the entire matrix is stored on the hard drive of each node, loaded into RAM and processed in parts. Independent Monte Carlo experiments for random column indices are distributed among MPI processes or OpenMP threads for both matrix storage approaches. The efficiency of parallel implementations is analyzed. Results are given for a system governed by dense matrices of size 10 4 and 10 5 .