Stochastic iterative projection methods for large linear systems

Abstract

We suggest a randomized version of the projection methods belonging to the class of a “row-action” methods which work well both for systems with quadratic nonsingular matrices and for overdetermined systems. These methods belong to a type known as Projection on Convex Sets methods. Here we present a method beyond the conventional Markov chain based Neumann–Ulam scheme. The main idea is in a random choice of blocks of rows in the projection method so that in average, the convergence is improved compared to the conventional periodic choice of the rows. We suggest an acceleration of the row projection method by using the Johnson–Lindenstrauss (J–L) theorem to find, among the randomly chosen rows, in a sense an optimal row. We extend this randomized method for solving linear systems coupled with systems of linear inequalities. Applied to finite-difference approximations of boundary value problems, the method appears to be an extremely efficient Random Walk algorithm whose convergence is exponential, and the cost does not depend on the dimension of the matrix. In addition, the algorithm calculates the solution in all grid points, and is easily parallelizable.