Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method

Abstract

Sparsified Randomization Monte Carlo (SRMC) algorithms for solving large systems of linear algebraic equations are presented. We construct efficient stochastic algorithms based on a probabilistic sampling of small size sub-matrices, or a randomized evaluation of a matrix-vector product and matrix iterations via a random sparsification of the matrix. This approach is beyond the standard Markov chain based Neumann–Ulam method which has no universal instrument to decrease the variance. Instead, in the new method, first, the variance can be decreased by increasing the number of the sampled columns of the matrix in play, and second, it is free of the restricted assumption of the Neumann–Ulam scheme that the Neumann series converges. We apply the developed methods to different stochastic iterative procedures. Application to boundary integral equation of the electrostatic potential theory is given where we develop a SRMC algorithm for solving the approximated system of linear algebraic equations, and compare it with the standard Random Walk on Boundary method.