On the Convergence of Iterative Methods in Stochastic Computational Environments

Abstract

Consider the computationally intensive task of solving large-scale linear systems, i.e., given an n → n matrix A and a vector b, compute the vector x that solves Ax = b. The numerical solution of large-scale linear systems plays a foundational role in many domains including those related to performance optimization, Markov processes, and dynamical systems. Iterative solution methods have emerged as a predominant class of algorithmic approaches for the e!cient numerical solution of large-scale linear-system problems, particularly approaches based on Krylov subspace methods. A key question for these iterative solution methods concerns the fundamental criteria for guaranteed convergence within a given level of accuracy, which have been well studied and well established for classical computing environments.